13
$\begingroup$

My understanding of P. vs NP is quite limited. I can understand P refers to an algorithm with an upper bound (big O) with order of growth $n^c$ for some constant c and variable n. My question is, do NP problems have a hypothesized lower bound order of growth (big Omega) of $c^n$ for deterministic machines? I can't find this stated anywhere and I'm trying to understand if this is something that is assumed or not.

Thanks.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$

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.