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.
No comments:
Post a Comment