Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $\mathcal{\Omega}(2^n)$.

  • can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?
  • 2
    $\begingroup$ It's not NP but it is NP-hard. $\endgroup$
    – user35734
    Oct 7, 2018 at 21:57
  • 3
    $\begingroup$ How do you know it's NP-hard? $\endgroup$ Oct 8, 2018 at 5:22
  • 1
    $\begingroup$ If you could show a problem to be in both $\mathcal{\Omega}(2^n)$ and in NP, you would have proven P$\neq$NP. $\endgroup$
    – kasperd
    Oct 8, 2018 at 16:14
  • 1
    $\begingroup$ @kasperd: We call that Merkle's Puzzles, but it should be excluded from P=?NP because the specific form yields no other with the same properties and an otherwise proof of P=NP probably eliminates any way of making Merkle's Puzzles that actually work as intended. The exponential time Merkle's Puzzles is also PSPACE for the intended user. $\endgroup$
    – Joshua
    Oct 8, 2018 at 18:49
  • 1
    $\begingroup$ @Joshua Merkle's puzzles are not exponential in dependence on input length. (Well, if we assume the solution for Alice is polynomial). $\endgroup$
    – rus9384
    Oct 8, 2018 at 23:43

2 Answers 2


No. For example, the halting problem has an $\Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).

The nondeterministic time hierarchy theorem shows that any NEXP-complete problem is another example (with $2^n$ potentially replaced by a smaller exponential function $c^{n^\epsilon}$).

NP is an upper bound on the complexity of a problem.

  • $\begingroup$ Could you give an example of a problem that is $\Omega(2^n)$ but not NP-hard? $\endgroup$ Oct 10, 2018 at 0:46
  • $\begingroup$ You can construct such a problem using diagonalization. $\endgroup$ Oct 10, 2018 at 4:04
  • $\begingroup$ Sorry, I don't follow. What is being diagonalized? Are we enumerating problems or algorithms? How does non-NP-hardness follow? $\endgroup$ Oct 10, 2018 at 5:31
  • 1
    $\begingroup$ You enumerate both Turing machines running in time $2^n$ and polynomial time reductions, making sure that none of the former compute your language, and none of the latter reduce SAT to your language. $\endgroup$ Oct 10, 2018 at 6:10

No. First, as Yuval points out, the problem could be much harder than the lower bound that you've proven.

Second, even if the problem takes time $\Theta(2^n)$ to solve, we don't know how this relates to $\mathbf{NP}$. It's possible that $\mathbf{P}=\mathbf{NP}$, in which case any problem in $\mathrm{TIME}[\Omega(2^n)]$ is certainly not in $\mathbf{NP}$ by the time hierarchy theorem. But even if $\mathbf{P}\neq\mathbf{NP}$, it's possible that the problem requires exponential space so isn't in $\mathbf{NP}$.

The best algorithms we know for $\mathbf{NP}$-complete problems take exponential time but you shouldn't assume that "in $\mathbf{NP}$" means "takes exponential time" or vice-versa.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.