# Assuming that SAT is decidable in $2^{O(\sqrt{n})}$, is every language in NP decidable in $2^{O(\sqrt{n})}$?

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

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.

-
The polynomial-time reduction can increase the instance size, so all you get is that every language in NP is decidable in time $2^{\sqrt{f(n)}}$ where $f(n)$ bounds the size of a reduction of that problem to SAT. – Colin McQuillan Dec 12 '11 at 11:44
Thanks for your comment, Colin. Does an increased instance size really affect the upper bound of the running time? For example, if $m$ is the length of the input produced by the reduction, every problem in NP would be decidable in $2^{O(\sqrt{m})}$, right? But isn't $O(\sqrt{m}) = O(\sqrt{n})$? – Zoidberg Dec 15 '11 at 16:47
No, you could have $m=n^2$. – Colin McQuillan Dec 15 '11 at 21:55
Colin, you should write up your comment as an answer so that it can be accepted. – Jeremy Hurwitz Dec 16 '11 at 1:19

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.

-