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 … R_{n}\). Meaning \(R_0 = \qty {s}\). Goal: convince \(V\) that \(t \not \in R_{n}\).
Define: \(r_{l} = |R_{l}|\). What’s the size of \(r_{l}\)? It’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’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\)
- …
- 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’s true of everything that’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’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\) “knows” \(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, …, n all present
- counts the number of “vertex i in p_l+1” which it claims it sees; checks the end of the “because …” 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