<p>Here are some papers that have results similar to the ones you ask about.</p>
<p>Ronald V. Book, On Languages Accepted in Polynomial Time, SIAM J. Comput. 1, 1972, pp. 281-287.</p>
<p>In this paper, we find Theorem 2 (There is no pair of real numbers r and s such that DSPACE(<span class="math-container">$n^r$</span>) <span class="math-container">$\subseteq$</span> P <span class="math-container">$\subseteq$</span> DSPACE(<span class="math-container">$n^s$</span>). (and similarly for NP).  In particular, neither P nor NP is equal to the class of context-sensitive languages.  Also, the Corollary after Theorem 3 says (in modern notation) E is not equal to NP.</p>
<p>A related paper is:</p>
<p>Ronald V. Book, Comparing Complexity Classes, J. Comput. and System Sciences 9, 1974, pp. 213-229.</p>
<p>In this paper, the Corollary at the top of page 223 says that P is not equal to NTIME(n^k) for any k.</p>
<p>Another Corollary lower down on the page states that E is not equal to PSPACE.  And on the next page we learn that NE is not equal to PSPACE and NE is not equal to EXP, and it is stated that some of these results also appear in Ron Fagin's Ph.D. Dissertation.</p>
<p>At one point in time, all of this was new and (even) surprising.</p>

CC BY-SA 4.0
2024-07-23T20:14:27.783Z
2024-07-23T20:14:27.783Z
Eric Allender
<p><a href="https://blog.computationalcomplexity.org/2024/06/e-versus-exp.html" rel="nofollow noreferrer">In a recent blog post</a>, Lance Fortnow dropped as a little exercise the task of proving <span class="math-container">$\mathsf{PSPACE} \neq \mathsf{E}$</span>, using the fact that <span class="math-container">$\mathsf{EXP}$</span> is the closure of <span class="math-container">$\mathsf{E}$</span> under poly-time many-one reductions, together with the Time Hierarchy Theorem. Do we know of a reference for this observation, or is it just folklore?</p>
<p>Similarly, it feels like an analogous argument gives you <span class="math-container">$\mathsf{P} \neq \mathsf{NTIME}(n^k)$</span> for every fixed <span class="math-container">$k$</span>, arguing that <span class="math-container">$\mathsf{NP}$</span> is the closure of <span class="math-container">$\mathsf{NTIME}(n^k)$</span> under poly-time many-one reductions. This surprised me a bit, since I thought we only knew how to prove <span class="math-container">$\mathsf{P}\neq\mathsf{NTIME}(n)$</span> and that argument broke for anything superlinear. Do we have a reference for this (or am I mistaken and this doesn't follow)? (<a href="https://complexityzoo.net/Complexity_Zoo:N#ntime" rel="nofollow noreferrer">The Complexity Zoo's entry for <span class="math-container">$\mathsf{NTIME}(n)$</span></a> points to the result <span class="math-container">$\mathsf{DTIME}(n) \subsetneq \mathsf{NTIME}(n)$</span>, which does not work for arbitrary <span class="math-container">$f(n)$</span>, but doesn't say anything about the separations from <span class="math-container">$\mathsf{P}$</span>.)</p>

CC BY-SA 4.0
2024-07-19T15:32:56.317Z
Re: 2nd para. Indeed $P \neq NTIME(n^k)$ by the same argument (P is closed under P reductions, NTIME(n^k) isn't), but, as Lance says in his blog post about PSPACE vs E, this argument doesn't tell you which (if any) is larger. It is still possible that P is (properly) contained in NTIME(n^k) (though it is not in NTIME(n), by [PPST]).
Joshua Grochow
CC BY-SA 4.0
2024-07-19T16:51:14.923Z
Good, thanks! Yes, this is exactly what I had in mind. So I guess these are just folklore, good to know.
Noel Arteche
CC BY-SA 4.0
2024-07-19T22:11:05.437Z
I mean, at this point it is folklore I guess, but I wouldn't be surprised if these occur in one of the early complexity papers, say where they first prove the Time Hierarchy or Nondet Time Hierarchy, or first introduced the class E.
Joshua Grochow
<reference-request><np><pspace><separation>
References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$
Noel Arteche
# References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$

(Asked by: username_0 on 2024-07-19)

[In a recent blog post](https://blog.computationalcomplexity.org/2024/06/e-versus-exp.html), Lance Fortnow dropped as a little exercise the task of proving $\mathsf{PSPACE} \neq \mathsf{E}$, using the fact that $\mathsf{EXP}$ is the closure of $\mathsf{E}$ under poly-time many-one reductions, together with the Time Hierarchy Theorem. Do we know of a reference for this observation, or is it just folklore?

Similarly, it feels like an analogous argument gives you $\mathsf{P} \neq \mathsf{NTIME}(n^k)$ for every fixed $k$, arguing that $\mathsf{NP}$ is the closure of $\mathsf{NTIME}(n^k)$ under poly-time many-one reductions. This surprised me a bit, since I thought we only knew how to prove $\mathsf{P}\neq\mathsf{NTIME}(n)$ and that argument broke for anything superlinear. Do we have a reference for this (or am I mistaken and this doesn't follow)? ([The Complexity Zoo's entry for $\mathsf{NTIME}(n)$](https://complexityzoo.net/Complexity_Zoo:N#ntime) points to the result $\mathsf{DTIME}(n) \subsetneq \mathsf{NTIME}(n)$, which does not work for arbitrary $f(n)$, but doesn't say anything about the separations from $\mathsf{P}$.)

**Tags:** reference-request, np, pspace, separation

> **Comments:**
> **username_1**: Re: 2nd para. Indeed $P \neq NTIME(n^k)$ by the same argument (P is closed under P reductions, NTIME(n^k) isn't), but, as Lance says in his blog post about PSPACE vs E, this argument doesn't tell you which (if any) is larger. It is still possible that P is (properly) contained in NTIME(n^k) (though it is not in NTIME(n), by [PPST]).  
> **username_0**: Good, thanks! Yes, this is exactly what I had in mind. So I guess these are just folklore, good to know.  
> **username_1**: I mean, at this point it is folklore I guess, but I wouldn't be surprised if these occur in one of the early complexity papers, say where they first prove the Time Hierarchy or Nondet Time Hierarchy, or first introduced the class E.  

---

## 1 answers

### Answer by username_2 on 2024-07-23. Score: 7 | Accepted answer

Here are some papers that have results similar to the ones you ask about.

Ronald V. Book, On Languages Accepted in Polynomial Time, SIAM J. Comput. 1, 1972, pp. 281-287.

In this paper, we find Theorem 2 (There is no pair of real numbers r and s such that DSPACE($n^r$) $\subseteq$ P $\subseteq$ DSPACE($n^s$). (and similarly for NP). In particular, neither P nor NP is equal to the class of context-sensitive languages. Also, the Corollary after Theorem 3 says (in modern notation) E is not equal to NP.

A related paper is:

Ronald V. Book, Comparing Complexity Classes, J. Comput. and System Sciences 9, 1974, pp. 213-229.

In this paper, the Corollary at the top of page 223 says that P is not equal to NTIME(n^k) for any k.

Another Corollary lower down on the page states that E is not equal to PSPACE. And on the next page we learn that NE is not equal to PSPACE and NE is not equal to EXP, and it is stated that some of these results also appear in Ron Fagin's Ph.D. Dissertation.

At one point in time, all of this was new and (even) surprising.


---

