12
$\begingroup$

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$?
$\endgroup$
  • 2
    $\begingroup$ It's not NP but it is NP-hard. $\endgroup$ – user35734 Oct 7 '18 at 21:57
  • 3
    $\begingroup$ How do you know it's NP-hard? $\endgroup$ – Yuval Filmus Oct 8 '18 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 '18 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 '18 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 '18 at 23:43
21
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you give an example of a problem that is $\Omega(2^n)$ but not NP-hard? $\endgroup$ – Mario Carneiro Oct 10 '18 at 0:46
  • $\begingroup$ You can construct such a problem using diagonalization. $\endgroup$ – Yuval Filmus Oct 10 '18 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$ – Mario Carneiro Oct 10 '18 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$ – Yuval Filmus Oct 10 '18 at 6:10
14
$\begingroup$

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.

$\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.