Skip to main content
edited tags
Link
Robin Kothari
  • 1.3k
  • 9
  • 16
add a comment
Source Link

If I say I can solve 3-SAT ( known to be NP-complete) in polynomial time, yet with the following 'little' proviso: Give me first $n$ the length of your 3-SAT formula, then give me some time on my own , then as soon as you give me your formula, I will answer in less that $n^k$.

The $k$ will be constant independent of $n$ ( thisthis is not parametrized complexity)

Implicitly: after you give me $n$, I may pre-calculate as much as I want (say $n^n$ or even much more) and I may also store some results as much as I want.

Question : is this equivalent to 3-SAT?

Comment : I cannot find a polynomial solution like : calculate all solutions store them on a tree and then retrieve on question . So it seems to be as 'difficult' as 3-SAT.

Note : I took 3 SAT but any NP-complete problem Q will do : define generically the variation Q' with the length of the instance of the problem Q given ahead of the instance.

If I say I can solve 3-SAT ( known to be NP-complete) in polynomial time, yet with the following 'little' proviso: Give me first $n$ the length of your 3-SAT formula, then give me some time on my own , then as soon as you give me your formula, I will answer in less that $n^k$.

The $k$ will be constant ( this is not parametrized complexity)

Implicitly: after you give me $n$, I may pre-calculate as much as I want (say $n^n$ or even much more) and I may also store some results as much as I want.

Question : is this equivalent to 3-SAT?

I took 3 SAT but any NP-complete problem Q will do : define generically the variation Q' with the length of the instance of the problem Q given ahead of the instance.

If I say I can solve 3-SAT ( known to be NP-complete) in polynomial time, yet with the following 'little' proviso: Give me first $n$ the length of your 3-SAT formula, then give me some time on my own , then as soon as you give me your formula, I will answer in less that $n^k$.

The $k$ will be constant independent of $n$ (this is not parametrized complexity)

Implicitly: after you give me $n$, I may pre-calculate as much as I want (say $n^n$ or even much more) and I may also store some results as much as I want.

Question : is this equivalent to 3-SAT?

Comment : I cannot find a polynomial solution like : calculate all solutions store them on a tree and then retrieve on question . So it seems to be as 'difficult' as 3-SAT.

Note : I took 3 SAT but any NP-complete problem Q will do : define generically the variation Q' with the length of the instance of the problem Q given ahead of the instance.

Source Link

Can knowing ahead the length of 3-SAT instance really help?

If I say I can solve 3-SAT ( known to be NP-complete) in polynomial time, yet with the following 'little' proviso: Give me first $n$ the length of your 3-SAT formula, then give me some time on my own , then as soon as you give me your formula, I will answer in less that $n^k$.

The $k$ will be constant ( this is not parametrized complexity)

Implicitly: after you give me $n$, I may pre-calculate as much as I want (say $n^n$ or even much more) and I may also store some results as much as I want.

Question : is this equivalent to 3-SAT?

I took 3 SAT but any NP-complete problem Q will do : define generically the variation Q' with the length of the instance of the problem Q given ahead of the instance.