I am wondering if given the time complexity of an NP-Complete problem or at least some information about it for example if $ SAT\in Time(2^{sqrt(n)})$ (hypothetically) could I assume that all languages in NP (which are clearly polynomial time reducible to SAT) are also $\in Time(2^{sqrt(n)})$

I believe the answer is false because I could basically pick any arbitrary class of exponential time functions and claim that all languages in NP are contained within it while it may actually belong to a class of higher power... but I'm not sure how to formulate this as a proof.


You are right. You can't draw that inference. Given the assumption that SAT can be solved in $O(2^{\sqrt{n}})$ time, it does not follow that all NP-complete problems can be solved in $O(2^{\sqrt{n}})$ time.

For instance, the reduction from the NP-complete problem to SAT might transform a problem instance of size $n$ to a SAT instance of size $n^2$, so applying the SAT algorithm to that would take $O(2^n)$ time. There are some reductions that preserve the size of the problem instance, and for those reductions, you will be able to solve them about as fast as SAT -- but as far as we know, not all NP-complete problems fall into that category.

You might enjoy reading about the exponential time hypothesis, which is the hypothesis that there is no such subexponential-time algorithm for SAT. Folks have studied the consequences of the exponential time hypothesis in depth (as well as the consequences of the negation of the exponential time hypothesis).

  • $\begingroup$ I think the even bigger implication being made my original statement, is not just that NP-Complete problems must be of the same time-complexity, but all problems in NP...I believe this because as a requirement to being an NP-Complete problem (SAT in this case) all problems in NP must be polynomial time reducible to it. Does this mean I can simply show an example of a problem in NP which has an upper bound time complexity greater than O(2^sqrt(n)) to disprove this claim? $\endgroup$ – IABP Dec 9 '13 at 16:23
  • 1
    $\begingroup$ @IABP, Yeah, it's false for "all NP-complete problems", and it's false for "all problems in NP". As best as we can tell, some problems in NP are easier than others: some take polynomial time, some take exponential time (at least if you assume the exponential time hypothesis), and some take subexponential time (at least as far as we can tell). $\endgroup$ – D.W. Dec 9 '13 at 17:11

Your Answer

