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$?
$\begingroup$
$\endgroup$
13
-
2$\begingroup$ It's not NP but it is NP-hard. $\endgroup$– user35734Oct 7, 2018 at 21:57
-
3$\begingroup$ How do you know it's NP-hard? $\endgroup$– Yuval FilmusOct 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$– kasperdOct 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$– JoshuaOct 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$– rus9384Oct 8, 2018 at 23:43
|
Show 8 more comments
2 Answers
$\begingroup$
$\endgroup$
4
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.
answered Oct 7, 2018 at 19:25
-
$\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
$\begingroup$
$\endgroup$
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.
answered Oct 7, 2018 at 20:23