Why NL is not L

Question

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?

Answer 1

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