23

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

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
Klim
  • 903
  • 4
  • 16

1 Answers1

31

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

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
  • 3
    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 – Luca Trevisan Mar 12 '11 at 02:22
  • @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. – arnab Mar 12 '11 at 15:33
  • 1
    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)$. – Ryan Williams Mar 12 '11 at 18:31
  • @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$? – Turbo May 08 '21 at 14:45