[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhnl.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "NL" source: https://www.jemoka.com/posts/kbhnl/ --- \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 <= 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’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’) \in E\), if \(c’\) 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’\), 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 \(\qty(G’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’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\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}\).