# If lower bound of a problem is exponential then is it NP?

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$$?
• It's not NP but it is NP-hard. – user35734 Oct 7 '18 at 21:57
• How do you know it's NP-hard? – Yuval Filmus Oct 8 '18 at 5:22
• If you could show a problem to be in both $\mathcal{\Omega}(2^n)$ and in NP, you would have proven P$\neq$NP. – kasperd Oct 8 '18 at 16:14
• @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. – Joshua Oct 8 '18 at 18:49
• @Joshua Merkle's puzzles are not exponential in dependence on input length. (Well, if we assume the solution for Alice is polynomial). – rus9384 Oct 8 '18 at 23:43

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.

• Could you give an example of a problem that is $\Omega(2^n)$ but not NP-hard? – Mario Carneiro Oct 10 '18 at 0:46
• You can construct such a problem using diagonalization. – Yuval Filmus Oct 10 '18 at 4:04
• Sorry, I don't follow. What is being diagonalized? Are we enumerating problems or algorithms? How does non-NP-hardness follow? – Mario Carneiro Oct 10 '18 at 5:31
• 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. – Yuval Filmus Oct 10 '18 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.