---
title: "NL"
type: concept
related: [Stconn, Proof Of Nl Conl, Certificates Based Intepretation Of Nl]
source: https://www.jemoka.com/posts/kbhnl/
confidence: high
status: active
---

\begin{equation} \text{NL} = \text{NSPACE} \qty( \log n) \end{equation}
See also Certificates-Based Intepretation of NL
problems in \(NL\) We can see \(L \subseteq NL\), because a TM is a NTM.
STCONN is in NL On input \(\qty(G, s,t)\), if \(s = t\), accept; otherwise,
currNode = 5 numSteps = 0 while steps &lt;= n non-deterministically choose a next node update currNode = w if w = t, accept set numSteps ++ reject so we just have to remember the current node. So this whole thing is \(O\qty(\log n)\).
three statements bounding NL space by P time \begin{equation} NL \subseteq P \end{equation}
key insights: STCONN in \(P\)
preliminaries:
Recap: \(L \subseteq P\): Recall the definition of configuration of TM \(M\) which solves \(L\) on input \(x\). Since \(M\) uses \(O \qty(\log n)\) space, then \(\leq n^{k}\) configurations because otherwise you&rsquo;d run out of space.
Yet, this time, a configuration can repeat on different branches within the non-determinism. Instead of a binary tree, instead, draw a digraph with each possible configuration corresponding at a vertex.
This is now a \(G\), such that \(V\) is all possible configurations; \(\qty(c, c&rsquo;) \in E\), if \(c&rsquo;\) is a next con fig coming from \(c\). For space \(S \qty(n)\), we have \(|V| = 2^{O(s \qty(n))}\)
By definition of non-deterministic TM, \(M\) accepts \(x\) IFF \(\exists\) path \(C_{\text{start}}\) to any accepting configuration.
We then take this graph, take each of the accepting configurations, and point each of the accepting configurations to a particular node \(C_{\text{accept}}\). We call this graph \(G&rsquo;\), suddenly this reduces to STCONN.
proof:
Let \(A \in \text{NL}\), for input \(x\), we spend poly time above to build graph \(G&rsquo;\) (we know this is poly time because there is only Poly N Verticies for space \(\log n\).
After this is done, \(x \in A\) if and only if \(\qty(G&rsquo;x, C_{\text{start}}, C_{\text{accept}}) \in \text{STCONN}\).
non-determinism buys quadratic savings \begin{equation} NL \subseteq \text{SPACE}\qty(\log^{2}\qty(n)) \end{equation}
key insights: STCONN in \(\log^{2}\qty(n)\)
preliminaries:
this is almost bounding space by time, but writing down the graph as a whole is decently difficult. we just have to solve this by never actually giving the Savitch&rsquo;s Algorithm the graph, and instead just giving it all the vertices; at \(k=0\), then we check once whether or not an edge is present.
To do this &ldquo;edge checking&rdquo;, we need to show that: let \(M\) be an NTM, given \(x\) and 2 configs \(c_1\) and \(c_2\), we can check in \(O\qty(\log n)\) space whether there is an edge between \(c_1\) and \(c_2\).
NL = coNL \begin{equation} \text{NL} = \text{coNL} \end{equation}
key insights: STCONN is in coNL
That is, we want to show that:
\begin{equation} \neg \text{STCONN} \in \text{NL} \end{equation}
in particular is that we want to show a short certificate for \(S\) and \(T\) are not connected.
see Proof of the Immerman-Szelepscenyi Theorem. Since \(\neg \text{STCONN} \in NL\), and since STCONN is NL complete, \(\text{NL} = \text{coNL}\).
