Space Complexity, Savitch's Theorem, and TQBF

By [L1], once the input $x$ is fixed a configuration of $M$ is determined by the current state, the $k$ head positions, and the symbols on the cells that have been visited so far: every unvisited work-tape cell is still blank, and every unvisited input-tape cell still carries its fixed symbol from $x$. By [L2], at most $s$ tape cells are ever visited in total.

Let $Q$ be the finite state set and let $\mathrm{\Gamma }$ be a common finite upper bound for the tape alphabets. Step 1.1 gives at most $\mathrm{\mid }Q\mathrm{\mid }$ choices for the state, at most $(s+1{)}^k$ choices for the head positions, and at most $\mathrm{\mid }\mathrm{\Gamma }{\mathrm{\mid }}^s$ choices for the symbols on the visited cells. Hence the total number of configurations that can arise on input $x$ is at most $\mathrm{\mid }Q\mathrm{\mid }(s+1{)}^k\mathrm{\mid }\mathrm{\Gamma }{\mathrm{\mid }}^s$.

Because $M$ is fixed, the constants $\mathrm{\mid }Q\mathrm{\mid }$, $k$, and $\mathrm{\mid }\mathrm{\Gamma }\mathrm{\mid }$ are fixed. For $s\ge 1$ there is therefore a constant $c_M$ with $\mathrm{\mid }Q\mathrm{\mid }(s+1{)}^k\mathrm{\mid }\mathrm{\Gamma }{\mathrm{\mid }}^s\le 2^{c_{M}s}$. This proves the claimed exponential bound.

For $i=0$, [L1] says ${\mathrm{Reach}}_0^G(u,v)$ holds exactly when $u=v$ or there is an arc $u\to v$. These are precisely the directed paths from $u$ to $v$ of lengths $0$ and $1$, hence of length at most $2^0$.

Assume the claim for $i-1$ with $i\ge 1$. If ${\mathrm{Reach}}_i^G(u,v)$ holds, [L1] gives a midpoint $z$ with ${\mathrm{Reach}}_{i-1}^G(u,z)$ and ${\mathrm{Reach}}_{i-1}^G(z,v)$. By the induction hypothesis there are directed paths from $u$ to $z$ and from $z$ to $v$, each of length at most $2^{i-1}$, and concatenating them gives a path from $u$ to $v$ of length at most $2^i$.

Conversely, suppose there is a directed path $u=v_0\to v_1\to \cdots \to v_{\mathrm{\ell }}=v$ with $\mathrm{\ell }\le 2^i$. Put $m:=\min (2^{i-1},\mathrm{\ell })$ and choose $z:=v_m$. Then the initial segment from $u$ to $z$ has length at most $2^{i-1}$, and the remaining segment from $z$ to $v$ has length $\mathrm{\ell }-m\le 2^{i-1}$. The induction hypothesis gives ${\mathrm{Reach}}_{i-1}^G(u,z)$ and ${\mathrm{Reach}}_{i-1}^G(z,v)$, so [L1] yields ${\mathrm{Reach}}_i^G(u,v)$.

Steps 1.1, 1.2, and 1.3 prove the equivalence for every $i$.

If $N=1$, the only possible path question is settled by ${\mathrm{Reach}}_0^G$. Suppose now that $N\ge 2$. Any directed path with repeated vertices can be shortened by deleting a directed cycle, so if $u$ reaches $v$ at all then $u$ reaches $v$ by a simple directed path. A simple directed path in an $N$-vertex digraph has length at most $N-1$, and $2^{\lceil {\log }_2(N-1)\rceil }\ge N-1$.

By [L1], every recursive call decreases the index $i$ by one, so starting from that initial $i$ yields recursion depth at most $i+1=O(\log N)$.

One stack frame stores the current vertices $u$, $v$, a midpoint candidate $z$, and the current index $i$. Each of these numbers is below $\max (N,i+1)$, so one frame uses $O(\log N)$ bits. Multiplying by the depth from step 2.1 gives total space $O({\log }^{2}N)$.

If $N\le 2^{cs(n)}$, then $\log N\le cs(n)$, and step 3.1 becomes $O(s(n{)}^2)$. The last sentence follows; [L2] records exactly the configuration bound that supplies such an $N$ in Savitch's theorem.

Let $M$ be the machine from [L1], and fix an input $x$ of length $n$. Form the directed configuration graph $G_x$: its vertices are the configurations of $M$ on $x$, and there is an arc $C\to C^{\mathrm{\prime }}$ exactly when one legal transition of $M$ moves from $C$ to $C^{\mathrm{\prime }}$. Let $C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ be the start configuration. Then $x\in L$ if and only if some accepting configuration is reachable from $C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ in $G_x$.

By [L2], $G_x$ has at most $N_x\le 2^{cs(n)}$ vertices for some constant $c$ depending only on $M$. Any directed path with repeated vertices can be shortened by deleting directed cycles, so $x\in L$ if and only if $C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ reaches some accepting configuration by a path of length at most $N_x-1$.

A deterministic simulator can enumerate candidate accepting configurations $C$ one at a time and run the bounded reachability procedure on the triple $(G_x,C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x),C)$ with an index large enough to cover $N_x-1$. By [L3], that test answers the reachability question correctly for each candidate $C$.

By [L4], each such reachability test uses $O(s(n{)}^2)$ space. The simulator never stores the whole graph: it keeps only the current input, one or two configurations, the midpoint candidate, and the recursion stack; adjacency in $G_x$ is recomputed from the transition function of $M$ when needed. The outer loop over candidate accepting configurations adds only $O(s(n))$ more space. Hence the overall deterministic decider uses $O(s(n{)}^2)$ space.

Since the input $x$ was arbitrary, $L\in \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n{)}^2)$. This proves $\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))\subseteq \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n{)}^2)$.

If $L\in \mathrm{N}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, then [L1] gives a polynomial $p$ with $L\in \mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(p(n))$. By [L2], $L\in \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(p(n{)}^2)\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, because the square of a polynomial is again a polynomial. Thus $\mathrm{N}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$.

The reverse inclusion $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{N}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ is immediate from [L1] because every deterministic machine is a special case of a nondeterministic one. Hence $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}=\mathrm{N}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$.

If $L\in \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, choose a deterministic polynomial-space decider $M$ for $L$ using [L1] and [L3]. Swapping the accepting and rejecting halting states of $M$ gives a deterministic polynomial-space decider for the complement of $L$. Therefore PSPACE is closed under complement.

If $\mathrm{\Phi }$ has no quantifiers, then by [L1] one only needs to evaluate a quantifier-free Boolean formula under a fully specified truth assignment. That can be done by a deterministic left-to-right parse using space polynomial in $\mathrm{\mid }\mathrm{\Phi }\mathrm{\mid }$.

Suppose $\mathrm{\Phi }$ begins with $\mathrm{\exists }x\mathrm{\Psi }(x)$. Recursively evaluate $\mathrm{\Psi }(0)$ and, if necessary, $\mathrm{\Psi }(1)$; accept exactly when at least one branch returns true. If instead $\mathrm{\Phi }$ begins with $\mathrm{\forall }x\mathrm{\Psi }(x)$, recursively evaluate both $\mathrm{\Psi }(0)$ and $\mathrm{\Psi }(1)$ and accept exactly when both are true. By [L1], this is exactly the truth definition of the quantified formula.

The recursion depth is at most the number of quantified variables, hence at most $\mathrm{\mid }\mathrm{\Phi }\mathrm{\mid }$. At each level the machine stores the current parse position and the current partial assignment, both of polynomial size. So the whole depth-first evaluation uses polynomial space, even though it may take exponential time.

By [L2], the deterministic recursive evaluator places TQBF in PSPACE.

By [L1], the base formula ${\mathrm{\Theta }}_0(U,V)$ has size $O(m)$.

For $i\ge 1$, [L1] shows that ${\mathrm{\Theta }}_i$ contains exactly one copy of ${\mathrm{\Theta }}_{i-1}$ plus only $O(m)$ new symbols coming from the variables $W,b,Y,Z$, the two equality tests, and the Boolean guards for $b=0$ and $b=1$. So if $s_i$ denotes the size of ${\mathrm{\Theta }}_i$, then $s_i\le s_{i-1}+cm$ for some constant $c$.

Starting from the $O(m)$ base bound in step 1.1 and iterating the recurrence from step 1.2 gives $s_i\le cm(i+1)$ for a suitable constant $c$. If $m$ is polynomial in the input length and $i=O(m)$, this bound is polynomial.

The membership part is exactly [L1]. So it remains to prove PSPACE-hardness.

Because $L\in \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, there is a deterministic machine $M$ deciding $L$ in space $p(n)$ for some polynomial $p$. Fix an input $x$ of length $n$. By [L2], configurations of $M$ on $x$ can be encoded by bit strings of length $m=O(p(n))$. If $M$ has more than one accepting configuration, adjoin one fresh sink vertex $t$ and one edge from every accepting configuration to $t$; this changes the encoding length by at most one bit and preserves acceptance.

By [L3], the resulting graph has at most $2^{cp(n)}$ vertices for some constant $c$. Choose $k:=cp(n)$ large enough that $2^k$ exceeds this number, and form the quantified Boolean formula ${\mathrm{\Phi }}_x:={\mathrm{\Theta }}_k(C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x),t)$ using [L4].

We claim that ${\mathrm{\Phi }}_x$ is true if and only if $M$ accepts $x$. The proof is by induction on the index used in [L4]. For $i=0$, ${\mathrm{\Theta }}_0(U,V)$ says exactly that $U=V$ or that one legal edge joins $U$ to $V$. For $i\ge 1$, the formula chooses a midpoint $W$ and then, by the universal choice of the selector bit $b$, forces one recursive call to certify the left half and one to certify the right half. Hence ${\mathrm{\Theta }}_i(U,V)$ is true exactly when there is a path from $U$ to $V$ of length at most $2^i$. With $U=C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ and $V=t$, this means exactly that $M$ accepts $x$.

By [L5], ${\mathrm{\Phi }}_x$ has polynomial size. Because the transition table of $M$ is fixed and the configuration length is polynomial, the formula ${\mathrm{\Phi }}_x$ can be written down from $x$ in polynomial time. Step 3.1 shows $x\in L⟺{\mathrm{\Phi }}_x\in \mathrm{T}\mathrm{Q}\mathrm{B}\mathrm{F}$, so by [L6] the map $x\mapsto {\mathrm{\Phi }}_x$ is a polynomial-time many-one reduction from $L$ to TQBF.

Steps 1.1 and 4.1 prove that TQBF is in PSPACE and PSPACE-hard. Therefore TQBF is PSPACE-complete.

If $\mathrm{\Phi }$ has no quantifiers, then [L1] says that $\mathrm{\Phi }$ is true exactly when its quantifier-free matrix is true, and [L2] says that this is exactly the condition for the existential player to win the zero-move game.

Suppose $\mathrm{\Phi }=\mathrm{\exists }x\mathrm{\Psi }(x)$. By [L1], $\mathrm{\Phi }$ is true if and only if at least one of $\mathrm{\Psi }(0)$ or $\mathrm{\Psi }(1)$ is true. By the induction hypothesis, that happens exactly when the existential player has a winning strategy for at least one of the two suffix games, and then the existential player wins the whole game by choosing that first move. Conversely, any winning strategy for the whole game determines such a first move.

Suppose instead $\mathrm{\Phi }=\mathrm{\forall }x\mathrm{\Psi }(x)$. By [L1], $\mathrm{\Phi }$ is true if and only if both $\mathrm{\Psi }(0)$ and $\mathrm{\Psi }(1)$ are true. By the induction hypothesis, that is equivalent to the existential player having a winning strategy after either first move of the universal player, which is exactly what [L2] means for the whole game.

Steps 1.1, 1.2, and 1.3 prove both directions of the equivalence.

To prove $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{A}\mathrm{P}$, it is enough by [L2] to show that TQBF lies in AP. On input a quantified Boolean formula, an alternating machine reads the quantifier prefix from left to right: at an existential quantifier it enters an existential state and chooses the bit, and at a universal quantifier it enters a universal state and branches over both bits. After the prefix is exhausted, it deterministically evaluates the matrix. By [L3], this machine accepts exactly the true formulas, so TQBF is in AP.

For the reverse inclusion, let $L\in \mathrm{A}\mathrm{P}$ and choose an alternating machine $M$ for $L$ running in time $p(n)$. On input $x$, a deterministic procedure evaluates the acceptance of the computation tree depth-first: at an accepting or rejecting leaf it returns the corresponding truth value; at an existential configuration it ORs the recursive values of the children; at a universal configuration it ANDs them. This exactly matches the acceptance rule in [L1].

Now let $L\in \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$. By [L2], there is a polynomial-time reduction $f$ from $L$ to TQBF. An alternating machine for $L$ first computes $f(x)$ deterministically and then runs the TQBF machine from step 1.1 on $f(x)$. This still uses only polynomial time, so [L1] gives $L\in \mathrm{A}\mathrm{P}$. Thus $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{A}\mathrm{P}$.

The recursion depth is at most $p(\mathrm{\mid }x\mathrm{\mid })$ because every branch halts within that many steps. One stack frame stores the current configuration and the remaining depth counter, both of polynomial size, so the whole depth-first evaluation uses polynomial space. Therefore $L\in \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$.

Steps 2.1 and 2.2 prove both containments, so $\mathrm{A}\mathrm{P}=\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$.

By [L1], Savitch's recursion examines one midpoint candidate and one shorter subproblem at a time, rather than materializing all candidates or all adjacency data at once.

By [L2], the whole recursion uses only polylogarithmic space in the number of configurations. An explicit storage of the whole configuration graph would require at least enough space to name all of its vertices, which is much larger than that bound in general. So the statement is false.

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$.