2
$\begingroup$

Assuming that we have an algorithm that decides SAT in $2^{O(\sqrt{n})}$, can every language in NP be decided in that time?

I had the following idea:

Because SAT is NP-complete, every language in NP can be reduced to it using a polynomial-time reduction. Therefore, every language in NP can be decided in $2^{O(\sqrt{n})} + O(polynomial)$ (the time that is required for the reduction). Because $2^{O(\sqrt{n})}$ grows asymptotically faster than $O(polynomial)$, every language in NP is decidable in $2^{O(\sqrt{n})}$.

Is that a proper explanation? I'm not quite sure about the last sentence.

  • 1
    Colin, you should write up your comment as an answer so that it can be accepted.2011-12-16

1 Answers 1

4

You've asked two questions: "does A imply B" and "is this argument that A implies B valid"? It is difficult to answer the first question - the title question - I'd guess it's not true, but for example it would be implied by P=NP.

However, I can answer the second question: the argument is invalid. The polynomial-time reduction can increase the instance size, so all you get is that every language in NP is decidable in time $2^{O(\sqrt{f(n)})}$ where f(n) bounds the size of a reduction of that problem to SAT.