6
$\begingroup$

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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
20
$\begingroup$

If you're allowed to do an exponential amount of work, then you might just solve SAT on all formulae of that size. Then you create an exponential size lookup table. Now when you're given the instance, just look it up and you've solved the problem.

On the other hand, if you insist that the stored data should only be of polynomial size, then the question you're asking is whether 3SAT is in P/poly. The notion of unbounded pre-computation based only on the input length is nicely captured by the concept called advice in complexity theory. The "/poly" after P basically means that the polynomial-time algorithm has access to a trusted polynomial-size string which depends only on the input length and not the instance. The advice string itself may be very hard to compute. All we need is the existence of such a string, not necessarily computability.

It is not known if 3SAT is in P/poly, and it's not known if this implies P = NP. However, it does imply that the polynomial hierarchy collapses to the second level by the Karp-Lipton theorem.

Lastly, P/poly has a nice intuitive description. It is the set of problems that can be solved by a polynomial-size circuit family.

Improve this answer
$\endgroup$
3
$\begingroup$

It sounds like your're trying to place SAT in P/poly (or P/exp or P/unbounded) rather than P.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ P/exp = P/unbounded = ALL. Once you have exponential advice, the advice can just contain the answers to all (exponentially many) potential instances of a given size. You never need more than exponential advice. $\endgroup$
    – Robin Kothari
    Commented Aug 29, 2010 at 19:51
  • $\begingroup$ Right. But the OP asked for unbounded advice strings, so I edited that in. $\endgroup$
    – Charles
    Commented Aug 29, 2010 at 21:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .