23
$\begingroup$

I wonder if there is any justification to believe that $NL=L$ or to believe that $NL\neq L$?

It is known that $NL \subset L^2$. The literature on derandomization of $RL$ is pretty convincing that $RL=L$. Does anyone know about some articles or ideas convincing that $NL\neq L$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
31
$\begingroup$

First, let me cite skepticism that $L \neq NL$. As it has been shown that undirected graph connectivity is in $L$ (Reingold), and that $NL=coNL$ (Immerman-Szelepcsényi), I think that confidence in $L \neq NL$ has only decreased. Some prominent researchers have never had a strong belief. For example, Juris Hartmanis (founder of the CS department at Cornell and Turing award winner) has said:

We believe that NLOGSPACE differs from LOGSPACE, but not with the same depth of conviction as for the other complexity classes. (Source)

I know he said similar things in the literature as far back as the 70's.

There is some evidence against $L=NL$, although it is circumstantial. There has been work on proving space lower bounds for $s$-$t$ connectivity (the canonical $NL$-complete problem) in restricted computational models. These models are strong enough to run the algorithm of Savitch's theorem (which gives an $O(\log^2 n)$ space algorithm) but are provably not strong enough to do asymptotically better. See the paper "Tight Lower Bounds for st-Connectivity on the NNJAG Model". These NNJAG lower bounds show that, if it's possible to beat Savitch's theorem and even get $NL \subseteq SPACE[o(\log^2 n)]$, one will certainly have to come up with an algorithm that's very different from Savitch.

Still, I don't know of any unlikely, unexpected formal consequences that come from $L=NL$ (except for the obvious ones). Again, this is primarily because we already know things like $NL=coNL$.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Ryan, can the models in which you can prove the $\Omega(\log^2 n)$ lower bound do undirected connectivity in $O(\log n)$ space? If they are non-uniform models, I guess it should be simple to implement an algorithm based on universal traversal sequences, even in a very restricted model $\endgroup$
    – Luca Trevisan
    Mar 12, 2011 at 2:22
  • $\begingroup$ @Luca, the paper Ryan cites by Edmonds et al. notes that undirected connectivity can be solved in $O(\log n)$ space and polynomial time by a randomized algorithm using universal traversal sequences. I suspect that it can be derandomized "a la" Reingold while staying inside the NNJAG model, but I haven't checked. $\endgroup$
    – arnab
    Mar 12, 2011 at 15:33
  • 1
    $\begingroup$ I think the model can do undirected connectivity on regular graphs in $O(\log n)$ space. Page 4 gives a description of the model. We are allowed $p$ pebbles to move around on the nodes of the graph (for us, let $p=1$), $q$ "states", and a transition function which takes a state and index of pebbled node, and outputs the index of an edge to move the pebble along. (The edges of a vertex $v$ are indexed $0,\ldots,d$.) Using $q=n^{O(1)}$ states we can encode a universal traversal sequence. The space usage of an NNJAG is defined to be $p \log n + \log q$ which in this case is $O(\log n)$. $\endgroup$
    – Ryan Williams
    Mar 12, 2011 at 18:31
  • $\begingroup$ @RyanWilliams If $TC^0=AC^0[6]$ and $TC^0=CC^0$ it would correspond to $LOGTIME$ hierarchy augmented by $MOD2$ and $MOD3$ containing $TC^0$. Would it imply $TC^0\neq NC^1$ (uniform or non-uniform) as $NC^1$ is $ALOGTIME$? Would it imply ${NC^1}^{\oplus NC^1}=NC^1=PP$ as $TC^0$ corresponds to $PP$? $\endgroup$
    – Turbo
    May 8, 2021 at 14:45

Your Answer

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

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