Suggest edit — Proof of the Immerman-Szelepscenyi Theorem

Title

Name

Note

---
title: "Proof of the Immerman-Szelepscenyi Theorem"
type: concept
source: https://www.jemoka.com/posts/kbhproof_of_nl_conl/
confidence: high
status: active
---

Suppose \(\qty(G,s,t) \in \neg \text{STCONN}\), meaning no path \(s \to t\) exists in \(G\).
setup For \(l \in \qty {0,1, \dots, n}\), define \(R_{l} \subseteq V\) is the set of all vertices readable from \(s\) in \(\leq l\) steps. \(R_0 \subseteq R_1 \subset &hellip; R_{n}\). Meaning \(R_0 = \qty {s}\). Goal: convince \(V\) that \(t \not \in R_{n}\).
Define: \(r_{l} = |R_{l}|\). What&rsquo;s the size of \(r_{l}\)? It&rsquo;s at most \(O\qty(\log \qty(n))\) size. Notice that storing \(R_{l}\) takes \(O\qty(n \log n)\) or at least \(O(n)\) space by storing either IDs or at least bitstring of everything.
certificates Here&rsquo;s the certificate for \(\neg \text{STCONN}\):
certificate 1: convince you of the size of \(r_1\) certificate 2: convince you of the size of \(r_2\) &hellip; certificate n: convince you of the size of \(r_n\) Finally, we compose them for a certificate for \(t\) is not reachable from \(s\).
operations As you move from left to right through the certificates, we use the certificate \(j\) to recover the value for \(r_{j}\) onto the tape (taking \(O\qty(\log n)\) space); then, we use the value \(r_{j}\) to validate the certificate \(j+1\). When we write \(r_{j+1}\), we erase the previous \(r_{j}\) value from tape. This uses at most \(O\qty(\log n)\) space to store a single \(r_{j}\).
lemma 1 Suppose \(V\) is convinced of the size of \(r_{n}\) (i.e. its on its work tape). There exist a certificate that \(t\) is not reachable from \(s\) (in \(n\) steps, but that&rsquo;s true of everything that&rsquo;s reachable).
The certificate here is the reachable paths from \(s\) to each of the \(r_{n}\) vertices, and we check that \(t\) is not one of the \(r_{n}\) things. Naively doing this has a potential cheat where a path is repeated twice, thereby hiding our target vertex. So, we pre-process the input graph by presenting the paths in increasing order of input vertices. So, a node can&rsquo;t be repeated since they would appear right next to each other. We only have to store a single vertex, which is size \(\log n\).
lemma 2 Suppose \(V\) &ldquo;knows&rdquo; \(r_{l}\); there is a certificate that convinces \(V\) of the value of \(r_{l+1}\).
requirements That is, we want verifier \(V\) which only uses \(O \qty(\log n)\) space, reaching the cert just once, and gets convinced that:
vertices 1, 2, &hellip;, n all present counts the number of &ldquo;vertex i in p_l+1&rdquo; which it claims it sees; checks the end of the &ldquo;because &hellip;&rdquo; claims certificates For each vertex \(v_{j}\), we issue a certificate for either \(v_{j} \in R_{l+1}\), or \(v_{j} \not \in R_{l+1}\).
\(v_{j} \in R_{l+1}\) we just give a path from \(s \to v_{j}\) of length \(\leq l+1\)
\(v_{j} \not \in R_{l+1}\) we show this by reminding \(V\) of \(R_{l}\) by enumerating every single path \(s \to v_{k}\) of length \(l\), \(V\) will then add one more step on top of each of these \(v_{k}\) and checking that \((v_{k}, v_{j})\) is not an edge