24
$\begingroup$

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 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$.

$\endgroup$
21
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Would natural proof obstacles not be an issue here ? I'm curious why that would be so. $\endgroup$ – Suresh Venkat Sep 29 '10 at 18:53
  • 6
    $\begingroup$ 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. $\endgroup$ – Noam Sep 29 '10 at 19:23
8
$\begingroup$

[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.

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. SIAM J. Comput., 28(4), 1460–1509, 1999

$\endgroup$
8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

this new paper was just highlighted by Luca Aceto in his blog as an EATCS best student paper at ICALP 2014 & has a novel way of separating NL/P:

  • Hardness Results for Intersection Non-Emptiness 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.

$\endgroup$

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.