9
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ I asked a subset of this question: cstheory.stackexchange.com/q/14159/4193 $\endgroup$ Commented Mar 17, 2013 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
    Commented Mar 17, 2013 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
    Commented Mar 17, 2013 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$ Commented Mar 18, 2013 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
    Commented Mar 18, 2013 at 2:04

1 Answer 1

12
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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