# ${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

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.

## 1 Answer

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

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