0
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ @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})$. $\endgroup$
    – Nathaniel
    Mar 12 at 12:21
  • $\begingroup$ Side note: $\mathsf{EXP}$ is not $\mathsf{DTIME}(2^n)$ but $\mathsf{DTIME}(2^{\text{poly}(n)})$. $\endgroup$ Mar 12 at 12:22
  • $\begingroup$ @Nathaniel Yeah, I realized it 10 seconds after posting, deleted that wrong comment… $\endgroup$ Mar 12 at 12:22

2 Answers 2

3
$\begingroup$

Yes, that is correct.

It is currently considered unlikely that NP = EXP.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

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

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