I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME.

Is anything known about the relationship between PSPACE and NEXPTIME? What about under the assumption that P = NP or that P != NP? Are the containments open problems from PSPACE all the way to NEXPTIME?

  • $\begingroup$ I believe you, but I don't follow your reasoning. P vs NP, and NP vs EXPTIME are both unknown, but P vs EXPTIME is known. $\endgroup$ – jmite Jul 9 '19 at 0:36
  • 1
    $\begingroup$ We know $PSPACE \subseteq EXP $ and we know $EXP \subseteq NEXP $, so we can immediately say $PSPACE \subseteq NEXP$. Since both $EXP$ vs $NEXP$ and $PSPACE$ vs $EXP$ are open questions, we can't say more than that $\endgroup$ – lox Jul 9 '19 at 8:11
  • $\begingroup$ @jmite You're right. I blame it being too close to bed time and, therefore, too long since I drank coffee. I believe the correct reasoning is "They're two complexity classes, so the answer to your title question is 'no'." 😉 $\endgroup$ – David Richerby Jul 9 '19 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.