|
3 |
edited tags
|
||
|
2 | add a comment | ||
|
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. |
||||
|
1 |
|
||
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.
|
||||

