<p>It made my day when my friend James told me that this thread from long ago was rekindled.  Thank you for that.</p>

<p>Also, I had an urge to share some interesting references that are relevant to L vs Log(DCFL) vs Log(CFL).  Have a great day!</p>

<p><a href="http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1">http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1</a></p>

<p><a href="http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true">http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true</a></p>

<p><a href="http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1">http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1</a></p>

<p><a href="http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata">http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata</a></p>

CC BY-SA 3.0
2014-05-15T05:59:30.513Z
2014-05-15T05:59:30.513Z
Michael Wehar
<p>[1] proves a lower bound for instances of mincost-flow whose bit-sizes are sufficiently large (but still linear) compared to the size of the graph, and furthermore proved that if one could show the same lower bound for inputs of sufficiently small bit-size it would imply $\mathsf{P} \neq \mathsf{NC}$ (and hence $\mathsf{P} \neq \mathsf{L}$). This is, at a high level, the same as Noam's answer in that it is about proving circuit depth lower bounds (=formula-size lower bounds), but seems to be a very different direction than Karchmer-Wigderson games.</p>

<p>In more detail, [1] shows the following. Using the same notation as in the paper, let $L$ denote the mincost-flow language. We can think of the mincost-flow language on $n$-vertex graphs, denoted $L(n)$, as a subset of $\mathbb{Z}^{k(n)}$ for some $k(n) = \Theta(n^2)$, with integers encoded by bit-strings. Let $B(a,n)$ denote the set of all vectors in $\mathbb{Z}^{k(n)}$ where each integer coordinate has bit-size at most $an$. Given a function $f(x_1, \dotsc, x_k)$ (we'll specify what kind of function later), we say that $f$ separates $L(n)$ within $B(a,n)$ if the points in $L(n) \cap B(a,n)$ are exactly those $\vec{x} \in B(a,n)$ such that $f(\vec{x}) = 1$.</p>

<blockquote>
  <p>Proposition [1, Proposition 7.3] If $L(n)$ is separated in $B(a,n)$ by $\det(M(\vec{x}))$ where $M$ is a matrix of size $\leq 2^{n/d}$ whose entries are (complex) linear combinations of $x_1, \dotsc, x_k$, and such that $a &lt; 1/(2d)$, then $\mathsf{P} \neq \mathsf{NC}$.</p>
</blockquote>

<p>The relationship between the bit-bound $an$ and the size bound $2^{n/d}$ is crucial here. In the same paper, he showed:</p>

<blockquote>
  <p>Theorem [1, Theorem 7.4] The hypothesis of the preceding proposition holds for all sufficiently large bit-bounds $a$.</p>
</blockquote>

<p>The proof of the above theorem uses some heavy hammers as black boxes, but is otherwise elementary (note: "elementary" $\neq$ "<em>easy</em>"). Namely, it uses the Milnor-Thom bound on the number of connected components of a real semialgebraic variety (the same bound used by Ben-Or to prove lower bounds on Element Distinctness / Sorting in the real computation tree model), the Collins decomposition (used to prove effective quantifier elimination over $\mathbb{R}$), a general position argument, and few other ideas. However, all of these techniques only depended on the degree of the polynomials involved, and so cannot be used to prove $\mathsf{P} \neq \mathsf{NC}$ as in the above Proposition (indeed, [1, Prop. 7.5] constructs a polynomial $g$ of the same degree as $\det$ such that the above proposition fails with $g$ in place of $\det$). Analyzing this situation and looking for properties that went beyond degree was one of the inspirations for GCT.</p>

<p>[1] K. Mulmuley. <a href="http://dx.doi.org/10.1137/S0097539794282930">Lower Bounds in a Parallel Model without Bit Operations</a>. SIAM J. Comput., 28(4), 1460–1509, 1999</p>

CC BY-SA 3.0
2014-05-08T21:36:47.373Z
2014-05-08T21:36:47.373Z
Joshua Grochow
<p>this new paper was just highlighted by Luca Aceto in his <a href="http://processalgebra.blogspot.com/2014/05/best-paper-awards-at-icalp-2014.html" rel="nofollow noreferrer">blog</a> as an EATCS best student paper at ICALP 2014 &amp; has a novel way of separating NL/P:</p>
<ul>
<li><p><a href="http://www.acsu.buffalo.edu/%7Emwehar/documents/mwehar_INE_2_15_14.pdf" rel="nofollow noreferrer">Hardness Results for Intersection Non-Emptiness</a> Wehar</p>
<blockquote>
<p>We carefully reexamine a construction of Karakostas, Lipton, and Viglas (2003) to show that the intersection
non-emptiness problem for DFA's (deterministic finite automata) characterizes
the complexity class NL. In particular, if restricted to a binary work tape alphabet, then there exist constants <span class="math-container">$c_1$</span> and <span class="math-container">$c_2$</span> such that for every <span class="math-container">$k$</span> intersection
non-emptiness for <span class="math-container">$k$</span> DFA's is solvable in <span class="math-container">$c_1 k \log(n)$</span> space, but is not solvable in
<span class="math-container">$c_2 k \log(n)$</span> space. We optimize the construction to show for an arbitrary number of DFA's intersection non-emptiness is not solvable in <span class="math-container">$o \left(  \frac{n}{\log(n) \log(\log(n))} \right) $</span> space. Furthermore, if there exists
a function <span class="math-container">$f(k) = o(k)$</span> such that for every <span class="math-container">$k$</span> intersection non-emptiness for <span class="math-container">$k$</span>
DFA's is solvable in <span class="math-container">$n^{f(k)}$</span> time, then P≠NL. If there does not exist a constant
<span class="math-container">$c$</span> such that for every <span class="math-container">$k$</span> intersection non-emptiness for <span class="math-container">$k$</span> DFA's is solvable in <span class="math-container">$n^c$</span>
time, then P does not contain any space complexity class larger than NL.</p>
</blockquote>
</li>
</ul>

CC BY-SA 3.0
2014-05-08T19:36:45.657Z
2014-05-30T07:47:40.923Z
2020-06-17T09:38:08.363Z
vzn
<p>Circuit depth lower bounds (equivalently, formula size lower bounds) are probably the most natural approach:  A Super-$\log^2(n)$ depth lower bound for a problem in $\mathsf P$ would separate $\mathsf P$ from $\mathsf L$, and the Karchmer-Wigderson communication complexity technique may be the natural one for that.</p>

CC BY-SA 2.5
2010-09-29T18:53:36.913Z
Would natural proof obstacles not be an issue here ? I'm curious why that would be so.
Suresh Venkat
CC BY-SA 2.5
2010-09-29T19:23:35.720Z
Yes, it definitely seems like such a proof would have to be "non-natural", but as far as I understand so would need to be the other approaches mentioned in the blog post.
Noam
CC BY-SA 3.0
2010-09-29T10:22:13.870Z
2014-05-08T20:26:16.503Z
2014-05-08T20:26:16.503Z
Noam
<p>It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$, $LogCFL$, $NC^i$, $SAC^i$, $AC^i$, $SC^i$. It is widely believed that $L \neq P$.</p>

<p>In one of my <a href="http://kintali.wordpress.com/2010/02/04/logspace-vs-polynomial-time/">blog posts</a> I mentioned two approaches (along with the corresponding conjectures) towards proving $L \neq P$. Both these approaches are based on branching programs and are 20 years apart !! Are there other approaches and/or conjectures towards separating $L$ from $P$ (or) separating any intermediate classes between $L$ and $P$.</p>

CC BY-SA 3.0
2012-05-12T16:48:34.653Z
think this problem [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence) is related
vzn
<cc.complexity-theory><lower-bounds><space-bounded>
Separating Logspace from Polynomial time
Shiva Kintali
# Separating Logspace from Polynomial time

(Asked by: username_0 on 2010-09-29)

It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$, $LogCFL$, $NC^i$, $SAC^i$, $AC^i$, $SC^i$. It is widely believed that $L \neq P$.

In one of my [blog posts](http://kintali.wordpress.com/2010/02/04/logspace-vs-polynomial-time/) I mentioned two approaches (along with the corresponding conjectures) towards proving $L \neq P$. Both these approaches are based on branching programs and are 20 years apart !! Are there other approaches and/or conjectures towards separating $L$ from $P$ (or) separating any intermediate classes between $L$ and $P$.

**Tags:** cc.complexity-theory, lower-bounds, space-bounded

> **Comments:**
> **username_1**: think this problem [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence) is related  

---

## 4 answers

### Answer by username_4 on 2010-09-29. Score: 22 | Accepted answer

Circuit depth lower bounds (equivalently, formula size lower bounds) are probably the most natural approach: A Super-$\log^2(n)$ depth lower bound for a problem in $\mathsf P$ would separate $\mathsf P$ from $\mathsf L$, and the Karchmer-Wigderson communication complexity technique may be the natural one for that.

> **Comments:**
> **username_5**: Would natural proof obstacles not be an issue here ? I'm curious why that would be so.  
> **username_4**: Yes, it definitely seems like such a proof would have to be "non-natural", but as far as I understand so would need to be the other approaches mentioned in the blog post.  

---

### Answer by username_2 on 2014-05-15. Score: 9

It made my day when my friend James told me that this thread from long ago was rekindled. Thank you for that.

Also, I had an urge to share some interesting references that are relevant to L vs Log(DCFL) vs Log(CFL). Have a great day!

<http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1>

<http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true>

<http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1>

<http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata>


---

### Answer by username_3 on 2014-05-08. Score: 8

[1] proves a lower bound for instances of mincost-flow whose bit-sizes are sufficiently large (but still linear) compared to the size of the graph, and furthermore proved that if one could show the same lower bound for inputs of sufficiently small bit-size it would imply $\mathsf{P} \neq \mathsf{NC}$ (and hence $\mathsf{P} \neq \mathsf{L}$). This is, at a high level, the same as username_4's answer in that it is about proving circuit depth lower bounds (=formula-size lower bounds), but seems to be a very different direction than Karchmer-Wigderson games.

In more detail, [1] shows the following. Using the same notation as in the paper, let $L$ denote the mincost-flow language. We can think of the mincost-flow language on $n$-vertex graphs, denoted $L(n)$, as a subset of $\mathbb{Z}^{k(n)}$ for some $k(n) = \Theta(n^2)$, with integers encoded by bit-strings. Let $B(a,n)$ denote the set of all vectors in $\mathbb{Z}^{k(n)}$ where each integer coordinate has bit-size at most $an$. Given a function $f(x\_1, \dotsc, x\_k)$ (we'll specify what kind of function later), we say that $f$ separates $L(n)$ within $B(a,n)$ if the points in $L(n) \cap B(a,n)$ are exactly those $\vec{x} \in B(a,n)$ such that $f(\vec{x}) = 1$.

> Proposition [1, Proposition 7.3] If $L(n)$ is separated in $B(a,n)$ by $\det(M(\vec{x}))$ where $M$ is a matrix of size $\leq 2^{n/d}$ whose entries are (complex) linear combinations of $x\_1, \dotsc, x\_k$, and such that $a < 1/(2d)$, then $\mathsf{P} \neq \mathsf{NC}$.

The relationship between the bit-bound $an$ and the size bound $2^{n/d}$ is crucial here. In the same paper, he showed:

> Theorem [1, Theorem 7.4] The hypothesis of the preceding proposition holds for all sufficiently large bit-bounds $a$.

The proof of the above theorem uses some heavy hammers as black boxes, but is otherwise elementary (note: "elementary" $\neq$ "*easy*"). Namely, it uses the Milnor-Thom bound on the number of connected components of a real semialgebraic variety (the same bound used by Ben-Or to prove lower bounds on Element Distinctness / Sorting in the real computation tree model), the Collins decomposition (used to prove effective quantifier elimination over $\mathbb{R}$), a general position argument, and few other ideas. However, all of these techniques only depended on the degree of the polynomials involved, and so cannot be used to prove $\mathsf{P} \neq \mathsf{NC}$ as in the above Proposition (indeed, [1, Prop. 7.5] constructs a polynomial $g$ of the same degree as $\det$ such that the above proposition fails with $g$ in place of $\det$). Analyzing this situation and looking for properties that went beyond degree was one of the inspirations for GCT.

[1] K. Mulmuley. [Lower Bounds in a Parallel Model without Bit Operations](http://dx.doi.org/10.1137/S0097539794282930). SIAM J. Comput., 28(4), 1460–1509, 1999


---

### Answer by username_1 on 2014-05-08. Score: 7

this new paper was just highlighted by Luca Aceto in his [blog](http://processalgebra.blogspot.com/2014/05/best-paper-awards-at-icalp-2014.html) as an EATCS best student paper at ICALP 2014 & has a novel way of separating NL/P:

* [Hardness Results for Intersection Non-Emptiness](http://www.acsu.buffalo.edu/%7Emwehar/documents/mwehar_INE_2_15_14.pdf) Wehar

  > We carefully reexamine a construction of Karakostas, Lipton, and Viglas (2003) to show that the intersection
  > non-emptiness problem for DFA's (deterministic finite automata) characterizes
  > the complexity class NL. In particular, if restricted to a binary work tape alphabet, then there exist constants $c\_1$ and $c\_2$ such that for every $k$ intersection
  > non-emptiness for $k$ DFA's is solvable in $c\_1 k \log(n)$ space, but is not solvable in
  > $c\_2 k \log(n)$ space. We optimize the construction to show for an arbitrary number of DFA's intersection non-emptiness is not solvable in $o \left( \frac{n}{\log(n) \log(\log(n))} \right) $ space. Furthermore, if there exists
  > a function $f(k) = o(k)$ such that for every $k$ intersection non-emptiness for $k$
  > DFA's is solvable in $n^{f(k)}$ time, then P≠NL. If there does not exist a constant
  > $c$ such that for every $k$ intersection non-emptiness for $k$ DFA's is solvable in $n^c$
  > time, then P does not contain any space complexity class larger than NL.


---

