# 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 May 15 '12 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 May 15 '12 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 May 15 '12 at 15:26
• Wikipedia has a nice page on this, namely on the time hierarchy theorem. – John Stalfos May 15 '12 at 17:20
• I think even $\mathsf{ZPP} = \mathsf{EXP}$ is open. – sdcvvc May 16 '12 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. – sdcvvc May 15 '12 at 20:53