On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

Question

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: http://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 01: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 02:04

score 12 · Answer 1 · answered Mar 17 '13 at 20:03

12

You can check the following paper:

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

answered Mar 17 '13 at 20:03

Abuzer Yakaryilmaz

3,707
1
20
38

3

A free online copy is here. – Kaveh Mar 17 '13 at 21:40

On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

1 Answers1