# On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!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.

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.

• I asked a subset of this question: cstheory.stackexchange.com/q/14159/4193 – argentpepper Mar 17 '13 at 20:59
• 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}$? question answer your questions? – Kaveh Mar 17 '13 at 21:39
• 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", 2012. – Kaveh Mar 17 '13 at 21:47
• @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 Mar 18 '13 at 1:07
• @Ryan, you are right, I was thinking of nonuniform $\mathsf{TC^0}$, what matters here is uniform version as you wrote. – Kaveh Mar 18 '13 at 2:04

Translational lemmas, polynomial time, and $(\log n)^j$-space by Ronald V. Book (1976).
• $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 )$.