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 \left(G, s,t\right), if s = t, accept; otherwise, currNode = 5 numSteps = 0 while steps <= 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\left(\log n\right). 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 \left(\log n\right) space, then \leq n^{k} configurations because otherwise you’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; \left(c, c’\right) \in E, if c’ is a next con fig coming from c. For space S \left(n\right), we have |V| = 2^{O(s \left(n\right))} 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’, suddenly this reduces to STCONN. proof: Let A \in \text{NL}, for input x, we spend poly time above to build graph G’ (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 \left(G’x, C_{\text{start}}, C_{\text{accept}}\right) \in \text{STCONN}. non-determinism buys quadratic savings \begin{equation} NL \subseteq \text{SPACE}\left(\log^{2}\left(n\right)\right) \end{equation} key insights: STCONN in \log^{2}\left(n\right) 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’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 “edge checking”, 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\left(\log n\right) 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:
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}.