2
$\begingroup$

Are there any EXPTIME-COMPLETE problems that cannot be proven to be PSPACE-COMPLETE?

$\endgroup$

1 Answer 1

5
$\begingroup$

No one knows. While it is conjectured that PSPACE $\ne$ EXPTIME, no one has any proof. In other words, it is consistent with all of our state of knowledge that PSPACE = EXPTIME. In particular:

  1. If PSPACE = EXPTIME, then every EXPTIME-complete problem is also PSPACE-complete.

  2. If PSPACE $\ne$ EXPTIME, then every EXPTIME-complete problem is not PSPACE-complete.

No one knows which of those two cases is true.

See, e.g., Why do we believe that PSPACE ≠ EXPTIME?.

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