# NP $\subsetneq$ EXP?

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

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

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.
• 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. Commented May 15, 2012 at 20:53