# complexity theory – Are NP problems lower bounded by exponential order of growth? First of all, every problem in P is in NP, and so we need to change your question to involve NP-complete problems rather than just NP problems.

The Exponential Time Hypothesis states that 3SAT requires exponential time $$c^m$$ for some constant $$c > 1$$, where $$m$$ is the number of variables. The Strong Exponential Time Hypothesis states that $$k$$SAT requires exponential time $$c_k^m$$, where $$c_k to 2$$.

However, your conjecture is unconditionally false. Consider the language $$L$$ consisting of all pairs $$langle x,y rangle$$ such that $$x$$ is a 3SAT instance on $$m$$ variables (in particular, $$m leq |x|$$), and $$y = 0^{|x|^{100}}$$. The language $$L$$ is clearly NP-complete, but it can be solved in time $$2^m mathit{poly}(n) = 2^{n^{1/100}} mathit{poly}(n)$$, where $$n$$ is the input size.

The Exponential Time Hypothesis does imply that every NP-complete problem requires time $$c^{n^alpha}$$, for some $$c>1$$ and $$alpha>0$$. This kind of running time is sometimes called subexponential time, but unfortunately this expression has several different interpretations, depending on context. Posted on