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.