We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$.
We also know that ${\bf E} \subset {\bf EXP}$, where
${\bf E} = \cup_c DTIME[2^{cn}]$ and
${\bf EXP} = \cup_c DTIME[2^{n^c}]$.

It has been shown by Book in [1972] that ${\bf E} \not = {\bf NP}$ and in 1974 [1974] that ${\bf E} \not = {\bf PSPACE}$.

${\bf Question}$: Why is it believed that there could be an exponential time algorithm for any problem in ${\bf PSPACE}$?

Edit: How is it still possible to argue that an NP-complete problem or a PSPACE-complete problem could possibly have a polynomial time algorithm or an exponential time algorithm when it is known that ${\bf P} \subset {\bf E} \subset {\bf EXP}$ and that ${\bf E} \not = {\bf NP}$ and ${\bf E} \not = {\bf PSPACE}$. The fact that ${\bf E} \not = {\bf NP}$ and ${\bf E} \not = {\bf PSPACE}$ should be able to disqualify one of these two possibilities. [The possibility that 1) A NP-Complete problem or a PSPACE-Complete problem having a Polynomial time algorithm. OR 2) A NP-Complete problem or a PSPACE-Complete problem having an Exponential time algorithm.]

[1972]: R. Book. On languages accepted in polynomial time. SIAM ournal on Computing, 1(4):281-287, 1972.
[1974]: R. Book. Comparing complexity classes. Journal of Computer and System Sciences, 3(9):213-229, 1974.


${\bf E} \not = {\bf NP}$ does not imply ${\bf E} \subset {\bf NP}$ nor ${\bf NP} \subset {\bf E}$. Similarly, ${\bf E} \not = {\bf PSPACE}$ does not imply ${\bf E} \subset {\bf PSPACE}$ nor ${\bf PSPACE} \subset {\bf E}$. You would need to show one of these containment's to be able to get a proper separation result out of those inequalities.

  • $\begingroup$ Added bonus... ${\bf E}$ is not closed under reductions. $\endgroup$ – Tayfun Pay Jul 2 '17 at 19:00

Your Answer

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

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