Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
1  
No, you could have $m=n^2$. –  Colin McQuillan Dec 15 '11 at 21:55
1  
Colin, you should write up your comment as an answer so that it can be accepted. –  Jeremy Hurwitz Dec 16 '11 at 1:19
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.