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

Improve this question
$\endgroup$
12
  • $\begingroup$ I remember that the answer is yes, but I don't remember the proof $\endgroup$
    – Belgi
    May 15, 2012 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, 2012 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, 2012 at 15:26
  • $\begingroup$ Wikipedia has a nice page on this, namely on the time hierarchy theorem. $\endgroup$
    – John Stalfos
    May 15, 2012 at 17:20
  • 3
    $\begingroup$ I think even $\mathsf{ZPP} = \mathsf{EXP}$ is open. $\endgroup$
    – sdcvvc
    May 16, 2012 at 14:04

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
9
  • 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.