Time complexity of languages that are polynomial time reducible to NP complete languages

Question

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.

Answer 1

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