patternMajor
If lower bound of a problem is exponential then is it NP?
Viewed 0 times
problemboundlowerexponentialthen
Problem
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$?
Solution
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.
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.
Context
StackExchange Computer Science Q#98277, answer score: 21
Revisions (0)
No revisions yet.