Suppose \left(G,s,t\right) \in \neg \text{STCONN}, meaning no path s \to t exists in G. setup For l \in \left\{0,1, \dots, n\right\}, 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 = \left\{s\right\}. 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\left(\log \left(n\right)\right) size. Notice that storing R_{l} takes O\left(n \log n\right) 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\left(\log n\right) 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\left(\log n\right) 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 \left(\log n\right) 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