3
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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).

$\endgroup$
  • $\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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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