Space Complexity, Savitch's Theorem, and TQBF: Examples and Counterexamples

The only directed path from $s$ to $t$ is $s\to a\to b\to t$, which has length $3$. Therefore [L2] gives ${\mathrm{Reach}}_1^G(s,t)$ false, because $2^1=2<3$.

Using midpoint $b$, [L1] reduces ${\mathrm{Reach}}_2^G(s,t)$ to ${\mathrm{Reach}}_1^G(s,b)$ and ${\mathrm{Reach}}_1^G(b,t)$. By [L2], the first holds because $s\to a\to b$ has length $2$, and the second holds because $b\to t$ has length $1$. Hence ${\mathrm{Reach}}_2^G(s,t)$ is true.

This makes the divide-and-conquer structure concrete: one midpoint splits the length-$3$ path into two shorter subproblems, exactly as the recursion predicts.

In the game of [L1], if Player E chooses $x=1$ on the first move, then the matrix $x\vee y$ is true regardless of whether Player A later chooses $y=0$ or $y=1$. So Player E has a winning strategy.

By [L2], step 1.1 implies that $\mathrm{\Phi }$ is true. The corresponding alternating machine from [L3] uses an existential state to choose $x$ and a universal state to branch over the two values of $y$; after the choice $x=1$, both universal branches accept.

This is the smallest nontrivial picture behind the inclusion $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{A}\mathrm{P}$ in AP equals PSPACE.

Take a graph with start vertex $s$, target vertex $t$, and many possible midpoints $z_1,\dots ,z_m$, but suppose only $z_7$ actually lies on a short path from $s$ to $t$. This is a legitimate instance of the claim in [L1].

Savitch's recursion tests the midpoint candidates one by one. At any moment it stores only the current pair of endpoints, the current candidate $z_j$, and the recursion stack for the shorter subproblems. When the test for $z_j$ fails, that local data is discarded before $z_{j+1}$ is tried. Hence no stage materializes the whole graph at once, even though the algorithm still eventually finds the successful midpoint $z_7$.