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

CC BY-SA 3.0
2017-07-02T19:00:44.050Z
Added bonus... ${\bf E}$ is not closed under reductions.
Tayfun Pay
CC BY-SA 3.0
2017-07-02T18:58:04.173Z
2017-07-02T18:58:04.173Z
Tayfun Pay
<p>We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$.<br>
We also know that ${\bf E} \subset {\bf EXP}$, where<br>
${\bf E} = \cup_c DTIME[2^{cn}]$ and<br>
${\bf EXP} = \cup_c DTIME[2^{n^c}]$.  </p>

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

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

<p>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.] </p>

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

<cc.complexity-theory><complexity-classes><time-complexity><p-vs-np>
${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$
Dave Schulman
# ${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

(Asked by: username_0 on 2017-07-02)

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.

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, p-vs-np

---

## 1 answers

### Answer by username_1 on 2017-07-02. Score: 6 | Accepted 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.

> **Comments:**
> **username_1**: Added bonus... ${\bf E}$ is not closed under reductions.  

---

