[Solved]: Time complexity of languages that are polynomial time reducible to NP complete languages

Problem Detail: 

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.

Asked By : IABP

Answered By : D.W.

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18767

3.2K people like this

 Download Related Notes/Documents