7
$\begingroup$

I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book resources do not seem to bring me an answer..

I just found a post similar to this, but I am not sure whether $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$.

$\endgroup$
  • $\begingroup$ I remember that the answer is yes, but I don't remember the proof $\endgroup$ – Belgi May 15 '12 at 15:03
  • 7
    $\begingroup$ The article on "computability" from the Stanford Encyclopedia of Philosophy says that "it is not even known that … NP is different from EXPTIME" and also "The only known proper inclusion from [ $P\subseteq NP\subseteq PSPACE \subseteq EXPTIME$ ] is that P is strictly contained in EXPTIME." But the article was last revised in 2008, so may not be current. $\endgroup$ – Mark Dominus May 15 '12 at 15:23
  • $\begingroup$ And the section on EXPTIME at the Complexity Zoo does not mention that it is strictly larger than PSPACE, only that "There exist oracles relative to which… EXP does not equal PSPACE". $\endgroup$ – Mark Dominus May 15 '12 at 15:26
  • $\begingroup$ Wikipedia has a nice page on this, namely on the time hierarchy theorem. $\endgroup$ – John Stalfos May 15 '12 at 17:20
  • 2
    $\begingroup$ I think even $\mathsf{ZPP} = \mathsf{EXP}$ is open. $\endgroup$ – sdcvvc May 16 '12 at 14:04
5
$\begingroup$

Strictly contained means $\subsetneq$, i.e. it is the definition, it is not a result. So what you are saying is $$\mathsf{NP} \subsetneq \mathsf{ExpTime} \implies \mathsf{NP} \subsetneq \mathsf{ExpTime}$$ which is trivially true.

If you are asking if $\mathsf{NP}\subsetneq \mathsf{ExpTime} $ then the answer is: it is unknown.

You may want to check the Wikipedia article about Exponential Time Hypothesis which many experts believe is true.

$\endgroup$
  • 4
    $\begingroup$ I think that the symbol “->” in the question is just a sloppy notation for “or equivalently,” not the symbol for logical implication, but I am not sure. $\endgroup$ – Tsuyoshi Ito May 15 '12 at 17:31
  • $\begingroup$ @Tsuyoshi, might be (though I have seen it used that way before), but it looks unlikely to me since the OP heard this. $\endgroup$ – Kaveh May 15 '12 at 17:34
  • 3
    $\begingroup$ Why did you mention the exponential time hypothesis? It is a stronger variant of the hypothesis P≠NP, and whether the ETH holds or not is not related to whether NP=EXP or NP≠EXP (as far as I know). $\endgroup$ – Tsuyoshi Ito May 15 '12 at 18:59
  • 3
    $\begingroup$ I would like to remark that it is known that $\mathsf{P} \neq \mathsf{EXP}$ and $\mathsf{NP} \neq \mathsf{NEXP}$ by time hierarchy theorem. $\endgroup$ – sdcvvc May 15 '12 at 20:53
  • 7
    $\begingroup$ The hypothesis “you need exponential time to solve NP-complete problems” has almost nothing to do with the current question, and the ETH is even farther from the current question. I think that your answer is confusing because it mentions the ETH as if it had anything to do with the question. $\endgroup$ – Tsuyoshi Ito May 16 '12 at 13:55

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.