<p>You can check the following paper:</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/0304397576900578">Translational lemmas, polynomial time, and $ (\log n)^j$-space</a> by Ronald V. Book (1976).</p>

<p>Figures 1 and 2 in the paper give the summary of what is known and what is unknown. </p>

<p>I put Theorem 3.10 in the paper here:</p>

<ul>
<li>$ DTIME(poly(n)) \neq DSPACE(poly(\log n)) $;</li>
<li>for every $ j \geq 1 $, $ DTIME(n^j) \neq DSPACE(poly(\log n)) $;</li>
<li>for every $ j,k \geq 1 $, $ DTIME(n^j) \neq DSPACE( (\log n)^k ) $.</li>
</ul>

CC BY-SA 3.0
2013-03-17T21:40:36.823Z
A free online copy is [here](http://www.cs.yale.edu/publications/techreports/tr32.pdf).
Kaveh
CC BY-SA 3.0
2013-03-17T20:03:16.960Z
2013-03-17T20:03:16.960Z
Abuzer Yakaryilmaz
<p>We know that $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$. From Savitch's Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$, and, from Space Hierarchy Teorem, $\mathcal{L}\neq\mathcal{L}^2$. So, as we don't know if $\mathcal L\neq\mathcal P$, we don't know if $\mathcal L^2\subseteq\mathcal P$, or do we know that $\mathcal L^2\not\subseteq\mathcal P$? Has anybody been trying to prove that $\mathcal L^2\subseteq\mathcal P$? What are the latest results, or efforts, in this way? I've been trying to write a survey on this topic, but haven't found anything relevant.</p>

<p>Furthermore, whether exists or not a $\mathcal{N\!P}$ problem which is not $\mathcal{N\!P}$-complete is an open question, and such existence would imply $\mathcal L\neq\mathcal{N\!P}$, as every $\mathcal L$ problem is complete for $\mathcal L$. But do we really not know that $\mathcal L\neq\mathcal{N\!P}$? Has anybody been trying to prove this? Again, what are the latest results, or efforts, in this way?</p>

<p>Maybe I'm missing something, or searching wrongly, but I couldn't find anyone working on the $\mathcal L^2\subseteq \mathcal P$ and $\mathcal L\neq\mathcal{N\!P}$ questions.</p>

CC BY-SA 3.0
2013-03-17T20:59:18.733Z
I asked a subset of this question: http://cstheory.stackexchange.com/q/14159/4193
argentpepper
CC BY-SA 3.0
2013-03-17T21:39:14.027Z
We don't know any separation between $\mathsf{TC^0}$ and $\mathsf{NExpTime}$. So any strict containment among classes between them is unknown. Does this plus @argentpepper's [What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?](http://cstheory.stackexchange.com/q/14159/4193) question answer your questions?
Kaveh
CC BY-SA 3.0
2013-03-17T21:47:50.800Z
Steve Cook with his colleagues has been working on an approach to separate $\mathsf{P}$ from $\mathsf{L}$. I think the following is their most recent published work on it:  Stephen Cook,
Pierre McKenzie,
Dustin Wehr,
Mark Braverman,
Rahul Santhanam,
 ["Pebbles and Branching Programs for Tree Evaluation"](http://dl.acm.org/citation.cfm?doid=2077336.2077337), 2012.
Kaveh
CC BY-SA 3.0
2013-03-18T01:07:08.280Z
@Kaveh We certainly know that **UNIFORM** $TC^0$ is different from $P^{\#P}$ -- cf. Allender's circuit lower bounds for the Permanent. (Uniform $TC^0$ is the version that is relevant to the present discussion.) But yes, even separating $NP$ from uniform-$TC^0$ is open.
Ryan Williams
CC BY-SA 3.0
2013-03-18T02:04:55.450Z
@Ryan, you are right, I was thinking of nonuniform $\mathsf{TC^0}$, what matters here is uniform version as you wrote.
Kaveh
<reference-request><complexity-classes><open-problem><hierarchy-theorems>
On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$
Leandro Zatesko
# On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

(Asked by: username_0 on 2013-03-17)

We know that $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$. From Savitch's Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$, and, from Space Hierarchy Teorem, $\mathcal{L}\neq\mathcal{L}^2$. So, as we don't know if $\mathcal L\neq\mathcal P$, we don't know if $\mathcal L^2\subseteq\mathcal P$, or do we know that $\mathcal L^2\not\subseteq\mathcal P$? Has anybody been trying to prove that $\mathcal L^2\subseteq\mathcal P$? What are the latest results, or efforts, in this way? I've been trying to write a survey on this topic, but haven't found anything relevant.

Furthermore, whether exists or not a $\mathcal{N\!P}$ problem which is not $\mathcal{N\!P}$-complete is an open question, and such existence would imply $\mathcal L\neq\mathcal{N\!P}$, as every $\mathcal L$ problem is complete for $\mathcal L$. But do we really not know that $\mathcal L\neq\mathcal{N\!P}$? Has anybody been trying to prove this? Again, what are the latest results, or efforts, in this way?

Maybe I'm missing something, or searching wrongly, but I couldn't find anyone working on the $\mathcal L^2\subseteq \mathcal P$ and $\mathcal L\neq\mathcal{N\!P}$ questions.

**Tags:** reference-request, complexity-classes, open-problem, hierarchy-theorems
> **Comments:**
> **username_1**: I asked a subset of this question: http://cstheory.stackexchange.com/q/14159/4193  
> **username_2**: We don't know any separation between $\mathsf{TC^0}$ and $\mathsf{NExpTime}$. So any strict containment among classes between them is unknown. Does this plus @argentpepper's [What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?](http://cstheory.stackexchange.com/q/14159/4193) question answer your questions?  
> **username_2**: Steve Cook with his colleagues has been working on an approach to separate $\mathsf{P}$ from $\mathsf{L}$. I think the following is their most recent published work on it:  Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam,  ["Pebbles and Branching Programs for Tree Evaluation"](http://dl.acm.org/citation.cfm?doid=2077336.2077337), 2012.  
> **username_3**: @Kaveh We certainly know that **UNIFORM** $TC^0$ is different from $P^{\#P}$ -- cf. Allender's circuit lower bounds for the Permanent. (Uniform $TC^0$ is the version that is relevant to the present discussion.) But yes, even separating $NP$ from uniform-$TC^0$ is open.  
> **username_2**: @Ryan, you are right, I was thinking of nonuniform $\mathsf{TC^0}$, what matters here is uniform version as you wrote.  

---

## 1 answers

### Answer by username_4 on 2013-03-17. Score: 12

You can check the following paper:

[Translational lemmas, polynomial time, and $ (\log n)^j$-space](http://www.sciencedirect.com/science/article/pii/0304397576900578) by Ronald V. Book (1976).

Figures 1 and 2 in the paper give the summary of what is known and what is unknown.

I put Theorem 3.10 in the paper here:

* $ DTIME(poly(n)) \neq DSPACE(poly(\log n)) $;
* for every $ j \geq 1 $, $ DTIME(n^j) \neq DSPACE(poly(\log n)) $;
* for every $ j,k \geq 1 $, $ DTIME(n^j) \neq DSPACE( (\log n)^k ) $.

> **Comments:**
> **username_2**: A free online copy is [here](http://www.cs.yale.edu/publications/techreports/tr32.pdf).  

---

