<p>You are right in noticing that the state space of an NL machine is only polynomially large (i.e. the number of reachable states is polynomial in the length <span class="math-container">$n$</span> of the input). A deterministic Logspace machine could enumerate all these states, and check whether one of them is accepting.</p>

<p>But this is not enough. To faithfully simulate the NL machine, the deterministic Logspace machine must decide whether there exists a path from the starting state to an accepting state. Such a path can have a length that is polynomial in <span class="math-container">$n$</span>. This is equivalent to deciding whether a vertex <span class="math-container">$s$</span> can reach a vertex <span class="math-container">$t$</span> in a given directed graph; this problem is sometimes called STCON (for <span class="math-container">$s-t$</span>-connectivity). This task is quite difficult, which is why no deterministic logspace procedure is known that solves it.</p>

<p>Let me illustrate the difficulty of the problem by showing that even with the use of randomness, it is not obvious how to solve this problem. That is, <span class="math-container">$RL\overset{?}{=}NL$</span> is unknown. A first attempt to solve STCON with randomness is to perform a random walk on the vertices of the graph, each time taking one of the outgoing edges with independent equal probability. But this approach fails, for example, on a path of <span class="math-container">$n$</span> vertices from <span class="math-container">$v_1$</span> to <span class="math-container">$v_n$</span>, where each vertex is connected to the first, i.e., <span class="math-container">$(v_i,v_1)\in E$</span>. The average time a random walk takes to reach <span class="math-container">$v_n$</span> from <span class="math-container">$v_1$</span> is <span class="math-container">$2^{O(n)}$</span>.</p>

CC BY-SA 4.0
2019-11-07T13:27:05.323Z
2019-11-07T13:27:05.323Z
Lieuwe Vinkhuijzen
<p>People don't know if NL=L or not yet. You showed that NL<span class="math-container">$\subseteq$</span> PSPACE, but it has nothing to do with L.</p>

CC BY-SA 4.0
2019-11-07T10:32:39.433Z
2019-11-07T10:32:39.433Z
Snjór
<p>I'm a beginner in learning complexity and get confused at NL.</p>

<p>NL is the class of languages that are decidable in logarithmic space on a nondeterministic Turing machine. In other words, NL = NSPACE(<span class="math-container">$\log{n}$</span>)</p>

<p>For nondeterministic single-tape Turing machine, there are <span class="math-container">$b^{\log{n}}$</span> leaves (where <span class="math-container">$b$</span> is the maximum number of legal choices). </p>

<p>For the first step, there is one space. For the second step, there are b space. For the third step, there are <span class="math-container">$b^2$</span> space. ... For the <span class="math-container">$\log{n}$</span> step, there are <span class="math-container">$b^{\log{n}}$</span>.</p>

<p>So there are <span class="math-container">$(b-b^{\log{n}})/(1-b) = O(b^{\log{n}}) = O(n)$</span> space in total. </p>

<p>Can we design a nondeterministic single-tape Turing machine that utilize the all the space it has like deterministic single-tape Turing machine and hence NL=L?</p>

<turing-machines><space-bounded><logspace>
Why NL is not L
Zachary HUANG
# Why NL is not L

(Asked by: username_0 on 2019-11-06)

I'm a beginner in learning complexity and get confused at NL.

NL is the class of languages that are decidable in logarithmic space on a nondeterministic Turing machine. In other words, NL = NSPACE($\log{n}$)

For nondeterministic single-tape Turing machine, there are $b^{\log{n}}$ leaves (where $b$ is the maximum number of legal choices).

For the first step, there is one space. For the second step, there are b space. For the third step, there are $b^2$ space. ... For the $\log{n}$ step, there are $b^{\log{n}}$.

So there are $(b-b^{\log{n}})/(1-b) = O(b^{\log{n}}) = O(n)$ space in total.

Can we design a nondeterministic single-tape Turing machine that utilize the all the space it has like deterministic single-tape Turing machine and hence NL=L?

**Tags:** turing-machines, space-bounded, logspace


---

## 2 answers

### Answer by username_1 on 2019-11-07. Score: 4 | Accepted answer

You are right in noticing that the state space of an NL machine is only polynomially large (i.e. the number of reachable states is polynomial in the length $n$ of the input). A deterministic Logspace machine could enumerate all these states, and check whether one of them is accepting.

But this is not enough. To faithfully simulate the NL machine, the deterministic Logspace machine must decide whether there exists a path from the starting state to an accepting state. Such a path can have a length that is polynomial in $n$. This is equivalent to deciding whether a vertex $s$ can reach a vertex $t$ in a given directed graph; this problem is sometimes called STCON (for $s-t$-connectivity). This task is quite difficult, which is why no deterministic logspace procedure is known that solves it.

Let me illustrate the difficulty of the problem by showing that even with the use of randomness, it is not obvious how to solve this problem. That is, $RL\overset{?}{=}NL$ is unknown. A first attempt to solve STCON with randomness is to perform a random walk on the vertices of the graph, each time taking one of the outgoing edges with independent equal probability. But this approach fails, for example, on a path of $n$ vertices from $v\_1$ to $v\_n$, where each vertex is connected to the first, i.e., $(v\_i,v\_1)\in E$. The average time a random walk takes to reach $v\_n$ from $v\_1$ is $2^{O(n)}$.


---

### Answer by username_2 on 2019-11-07. Score: 2

People don't know if NL=L or not yet. You showed that NL$\subseteq$ PSPACE, but it has nothing to do with L.


---

