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.

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

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 ) $.
  • 3
    $\begingroup$ A free online copy is here. $\endgroup$ – Kaveh Mar 17 '13 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.