<p>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:</p>

<blockquote>
  <p>We believe that NLOGSPACE differs from LOGSPACE, but not with the same depth of conviction as for the other complexity classes. <a href="http://portal.acm.org/ft_gateway.cfm?id=602402&amp;type=pdf">(Source)</a></p>
</blockquote>

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

<p>There is <em>some</em> 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.5221">"Tight Lower Bounds for st-Connectivity on the NNJAG Model"</a>. 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. </p>

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

CC BY-SA 2.5
2011-03-12T02:22:48.067Z
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
CC BY-SA 2.5
2011-03-12T15:33:04.683Z
@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
CC BY-SA 2.5
2011-03-12T18:31:34.400Z
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
CC BY-SA 4.0
2021-05-08T14:45:39.013Z
@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
CC BY-SA 2.5
2011-03-11T22:56:50.397Z
2011-03-11T22:56:50.397Z
Ryan Williams
<p>I wonder if there is any justification to believe that $NL=L$ or to believe that $NL\neq L$?</p>

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

<cc.complexity-theory><reference-request><complexity-classes><space-bounded>
Is there any justification to believe that $NL\neq L$?
Klim
# Is there any justification to believe that $NL\neq L$?

(Asked by: username_0 on 2011-03-11)

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

**Tags:** cc.complexity-theory, reference-request, complexity-classes, space-bounded


---

## 1 answers

### Answer by username_1 on 2011-03-11. Score: 31 | Accepted answer

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)](http://portal.acm.org/ft_gateway.cfm?id=602402&type=pdf)

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"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.5221). 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$.

> **Comments:**
> **username_2**: 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  
> **username_3**: @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.  
> **username_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)$.  
> **username_4**: @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$?  

---

