# If we prove that NP = EXP, does that automatically prove that P != NP?

If P = DTIME(n^c) and EXP = DTIME(2^n), and we prove that NP = EXP, then it means that NP = DTIME(2^n). According to the time hierarchy theorem, the set of languages decided in O(f(n)) is bigger than those decided in o(f(n)). So does that not imply P != NP?

• @JeanAbouSamra Not quite: what you describe is $\mathsf{E}$. A correct definition would be $\mathsf{EXP} = \bigcup\limits_{k\in\mathbb{N}}\mathsf{DTIME}(2^{n^k})$. Mar 12 at 12:21
• Side note: $\mathsf{EXP}$ is not $\mathsf{DTIME}(2^n)$ but $\mathsf{DTIME}(2^{\text{poly}(n)})$. Mar 12 at 12:22
• @Nathaniel Yeah, I realized it 10 seconds after posting, deleted that wrong comment… Mar 12 at 12:22

Yes. We know that $$\mathsf{P}\subseteq\mathsf{NP}\subseteq \mathsf{EXP}$$. However, by diagonalization we know that $$\mathsf{P} \neq \mathsf{EXP}$$, hence one of the inclusions must be strict. So it follows that showing $$\mathsf{NP}=\mathsf{EXP}$$, implies $$\mathsf{P}\neq \mathsf{NP}$$.