PSPACE — Quantified Boolean Formula: Exercises

Two more symbols carry this whole page, so let us re-anchor them in plain words before we start:

We evaluate a formula by drawing its game tree: one branching level per variable, ∃-levels combine children with OR, ∀-levels combine with AND. The figure below fixes that vocabulary once.

Figure s01 — game tree of $\exists x \forall y (x \lor y)$ . The amber root is the $\exists x$ move; its two cyan children are the $\forall y$ nodes reached by choosing $x = 0$ (left) or $x = 1$ (right); the four white leaves plug in both values of $y$ and compute $x \lor y$ . Reading it: each $\forall y$ node ANDs its two leaves, and the $\exists x$ root ORs its two children. On the right branch ( $x = 1$ ) both leaves equal $1$ , so that $\forall$ -node is TRUE, and one true child is all the $\exists$ -root needs ⇒ the whole formula is TRUE. (If the image fails to load, the alt-text is "game tree with an OR-root over two AND-nodes over four leaves".)

Figure — PSPACE — Quantified Boolean Formula

L1 · Recognition

Exercise 1.1

Which of these are QBF in prenex form (as defined in PSPACE — Quantified Boolean Formula)? For each, say if it is a closed formula (no free variables), and if so give its truth value.

(a) $\exists x (x \lor \neg x)$
(b) $\forall x (x \land y)$
(c) $\exists x \forall y (x \lor y)$

Recall Solution 1.1

A prenex QBF is all quantifiers up front, then a quantifier-free body; closed means every variable is bound by some quantifier.

(a) Prenex ✔. Closed ✔ ( $x$ is bound). Value: $x = 0 \Rightarrow 0 \lor 1 = 1$ ; already one true branch, and $\exists =$ OR, so TRUE.

(b) Prenex ✔ but NOT closed: $y$ is free (no quantifier binds it). A formula with a free variable is not a QBF you can assign a truth value to — its answer depends on $y$ . So it has no single truth value.

(c) Prenex ✔. Closed ✔. Evaluate: try $x = 1$ , then $\forall y (1 \lor y)$ : $y = 0 \Rightarrow 1$ , $y = 1 \Rightarrow 1$ , both hold. ∃ found a good $x$ ⇒ TRUE.

L2 · Application

Exercise 2.1

Evaluate $\forall x \exists y (x \leftrightarrow y)$ by unrolling the recursion. Show both ∀-branches. ( $a \leftrightarrow b$ means " $a$ equals $b$ ": true when both bits match.)

Recall Solution 2.1

$\forall =$ AND over $x \in {0, 1}$ , so we must check both branches and AND them.

$x = 0$ : need $\exists y (0 \leftrightarrow y)$ . Pick $y = 0$ : $0 \leftrightarrow 0 = 1$ . ∃ succeeds ⇒ T.
$x = 1$ : need $\exists y (1 \leftrightarrow y)$ . Pick $y = 1$ : $1 \leftrightarrow 1 = 1$ . ∃ succeeds ⇒ T.

Both ∀-branches true, $T \land T =$ TRUE.

Notice the choice of $y$ depended on $x$ ( $y = x$ ). That dependency is exactly what $\forall\exists$ order allows.

Exercise 2.2

Evaluate $\forall x \exists y (x \land y)$ .

Recall Solution 2.2

$x = 0$ : $\exists y (0 \land y)$ . For $y = 0$ : $0$ ; for $y = 1$ : $0$ . Every value gives $0$ , so ∃ (an OR over both) $= 0 \lor 0 =$ F.
One ∀-branch already false. $\forall$ is an AND, so $F \land (anything) =$ FALSE.

We may stop early: ∀ needs all branches true; the first failure decides it.

L3 · Analysis

Exercise 3.1

Are these two formulas equivalent? Decide each and explain the difference. $A : \exists x \forall y (x \lor y) B : \forall y \exists x (x \lor y)$

Recall Solution 3.1

$A$ : ∃ commits to one $x$ first, then it must beat every $y$ .

$x = 1$ : $\forall y (1 \lor y)$ = T for $y = 0$ and $y = 1$ . ⇒ A is TRUE.

$B$ : ∀ moves first, then ∃ picks $x$ knowing $y$ .

$y = 0$ : pick $x = 1$ ⇒ $1 \lor 0 = 1$ . T.
$y = 1$ : pick $x = 0$ ⇒ $0 \lor 1 = 1$ . T. ⇒ B is TRUE.

Both true here — but that is a coincidence of this body. The order still matters in general (see 3.2). In $B$ , $x$ may depend on $y$ ; in $A$ one fixed $x$ must work for all $y$ .

Exercise 3.2

Give a body $ϕ (x, y)$ over the booleans where $\exists x \forall y ϕ \neq = \forall y \exists x ϕ$ . State both truth values.

Recall Solution 3.2

Take $ϕ (x, y) = (x \leftrightarrow y)$ (" $x$ equals $y$ ").

$\exists x \forall y (x \leftrightarrow y)$ : ∃ fixes one $x$ that must equal every $y$ .

$x = 0$ : fails at $y = 1$ . $x = 1$ : fails at $y = 0$ . No fixed $x$ works ⇒ FALSE.

$\forall y \exists x (x \leftrightarrow y)$ : ∀ picks $y$ , then ∃ picks $x = y$ .

$y = 0 \Rightarrow x = 0$ : T. $y = 1 \Rightarrow x = 1$ : T. ⇒ TRUE.

So $FALSE \neq = TRUE$ : swapping $\exists$ and $\forall$ changed the answer. The mechanism: in $\forall y \exists x$ , the winning $x$ is a function of $y$ ; in $\exists x \forall y$ it must be one constant.

L4 · Synthesis

Exercise 4.1

A QBF with $n$ variables has a game tree of depth $n$ . State (i) how many leaves the tree has, (ii) the time the recursive evaluator takes, and (iii) the space it uses. Explain why space $≪$ time. (Here $ψ$ denotes the quantifier-free body of the formula, and $∣ ψ ∣$ is its size — the number of symbols we must store to evaluate one leaf.)

Recall Solution 4.1

Each variable branches into $2$ values, over $n$ levels. Throughout, $∣ ψ ∣$ is the size of the quantifier-free body $ψ$ — the fixed chunk of text we keep in memory to compute any single leaf.

(i) Leaves: $2^{n}$ .
(ii) Time: we visit essentially every node ⇒ $Θ (2^{n})$ work (times $∣ ψ ∣$ per leaf eval).
(iii) Space: the recursion evaluates the first child, keeps one bit of its result, then reuses the same memory for the second child. Only the current root-to-node path lives in memory. Depth is $n$ , each frame stores $O (∣ ψ ∣)$ , so $S (n) = S (n - 1) + O (∣ ψ ∣), S (0) = O (∣ ψ ∣) \Rightarrow S (n) = O (n ∣ ψ ∣) .$

Why space $≪$ time: we never hold two subtrees at once — we overwrite. Time must still touch all $2^{n}$ leaves, but space only needs one path of length $n$ . This memory-reuse is precisely why $TQBF \in PSPACE$ . See PSPACE and Polynomial Space.

Figure s02 — space vs time on a depth- $n$ tree. The full cyan binary tree ( $n = 4$ shown) has $2^{n} = 16$ leaves at the bottom; visiting them all is the $Θ (2^{n})$ time cost. The single amber path from root to one leaf is the only thing held in memory at any instant — depth $n$ , reused (overwritten) for every branch. So the picture literally shows a fat tree (time) versus one thin path (space). (If the image fails to load, the alt-text is "large binary tree with one highlighted root-to-leaf path".)

Exercise 4.2

Write $3 -SAT$ on the clause set $ϕ = (x_{1} \lor x_{2}) \land (\neg x_{1} \lor x_{3})$ as a member of TQBF and confirm membership. (Recall from SAT and NP-completeness that SAT is the all-∃ case.)

Recall Solution 4.2

$ϕ \in SAT ⟺ \exists x_{1} \exists x_{2} \exists x_{3} [(x_{1} \lor x_{2}) \land (\neg x_{1} \lor x_{3})] \in TQBF .$

Find one satisfying assignment: try $x_{1} = 1, x_{3} = 1$ : clause 1 $= 1 \lor x_{2} = 1$ ; clause 2 $= 0 \lor 1 = 1$ . Both clauses true ⇒ the all-∃ formula is TRUE ⇒ $⟨ ψ ⟩ \in TQBF$ .

L5 · Mastery

Exercise 5.1

In the PSPACE-hardness reduction we encode reachability as a QBF. The naïve rule is $R_{t} (a, b) = \exists m [R_{t - 1} (a, m) \land R_{t - 1} (m, b)] .$ Let $∣ R_{t} ∣$ be the formula size. Write the recurrence for $∣ R_{t} ∣$ , solve it, and say why the reduction fails. Then state the Savitch $\forall$ -folded fix and its size recurrence.

Recall Solution 5.1

Setup and notation. Suppose the original PSPACE machine runs in space $s = n^{k}$ , where $n$ is the input length and $k$ is the constant exponent from $SPACE (n^{k})$ . A configuration (full machine state) fits in $O (s)$ bits, so there are at most $2^{O (s)}$ configurations, and any accepting run has length $\leq 2^{O (s)}$ . We build $R_{t} (a, b)$ meaning "config $a$ reaches config $b$ in $\leq 2^{t}$ steps"; we need it up to $t = O (s)$ levels.

Two pieces of notation used below, spelled out:

$\forall (u, v)$ means two nested universals $\forall u \forall v$ — one quantifier per coordinate of the pair. It is pure shorthand; the scope of both covers the whole bracket that follows. (Each of $u, v$ is itself a block of bits encoding a configuration; " $\forall$ over a configuration" is in turn shorthand for $\forall$ over each of its bits.)
$(u, v) = (a, m)$ is pair-equality, itself a Boolean formula: it is $⋀_{i} (u_{i} \leftrightarrow a_{i}) \land ⋀_{j} (v_{j} \leftrightarrow m_{j})$ — every bit of $u$ matches the corresponding bit of $a$ AND every bit of $v$ matches $m$ . So " $=$ on pairs" is just a big conjunction of bit-wise $\leftrightarrow$ ; nothing new is assumed.

Naïve size. $R_{t - 1}$ appears twice, so $∣ R_{t} ∣ = 2 ∣ R_{t - 1} ∣ + c .$ Unrolling: $∣ R_{t} ∣ = 2^{t} ∣ R_{0} ∣ + c (2^{t} - 1) = Θ (2^{t})$ . With $t = O (s) = O (n^{k})$ that is $2^{O (n^{k})}$ — exponential formula size. A reduction must run in polynomial time and thus produce a polynomial-size output, so this fails.

Savitch fix (∀-folding). Reuse a single copy of $R_{t - 1}$ by quantifying a generic endpoint pair $(u, v)$ with $\forall u \forall v$ : $R_{t} (a, b) = \exists m \forall u \forall v [((u, v) = (a, m) \lor (u, v) = (m, b)) \Rightarrow R_{t - 1} (u, v)] .$ Now $R_{t - 1}$ appears once, so $∣ R_{t} ∣ = ∣ R_{t - 1} ∣ + c^{'} \Rightarrow ∣ R_{t} ∣ = ∣ R_{0} ∣ + c^{'} t = O (s^{2}) .$ Polynomial in $n$ . This is Savitch's Theorem written in quantifiers: the $\forall$ lets one subformula serve both halves of the divide-and-conquer.

Exercise 5.2

For the naïve rule with $c = 1$ and $∣ R_{0} ∣ = 1$ , compute $∣ R_{5} ∣$ exactly. Then for the folded rule with $c^{'} = 1, ∣ R_{0} ∣ = 1$ , compute $∣ R_{5} ∣$ . Compare.

Recall Solution 5.2

Naïve $∣ R_{t} ∣ = 2∣ R_{t - 1} ∣ + 1, ∣ R_{0} ∣ = 1$ : this is $∣ R_{t} ∣ = 2^{t + 1} - 1$ .

$∣ R_{5} ∣ = 2^{6} - 1 = 63$ .

Folded $∣ R_{t} ∣ = ∣ R_{t - 1} ∣ + 1, ∣ R_{0} ∣ = 1$ : linear, $∣ R_{t} ∣ = t + 1$ .

$∣ R_{5} ∣ = 6$ .

$63$ vs $6$ at just $t = 5$ . The gap is $2^{t}$ -vs- $t$ ; at $t = s = n^{k}$ the naïve one is astronomically larger. This single design choice is the difference between a valid poly-time reduction and a broken exponential one.

Exercise 5.3

Interpret $\exists x_{1} \forall x_{2} \exists x_{3} ϕ$ as a 2-player game (see Two-Player Games and Game Trees). Who moves when, and what does the formula being true mean? Connect this to the Polynomial Hierarchy.

Recall Solution 5.3

Turns (read left to right): the ∃-player (Prover) sets $x_{1}$ ; the ∀-player (Spoiler) then sets $x_{2}$ trying to break $ϕ$ ; the Prover sets $x_{3}$ in response. Perfect information, fixed length.

Truth = winning strategy: the formula is true $⟺$ the ∃-player has a strategy that makes $ϕ$ hold no matter how the Spoiler plays $x_{2}$ . Concretely: $\exists x_{1}$ such that for all $x_{2}$ there exists $x_{3}$ with $ϕ$ true.

Hierarchy link: a fixed number of quantifier alternations $Σ_{k} / Π_{k}$ defines the levels of the Polynomial Hierarchy. Allowing unboundedly many alternations (as full QBF does) is what lifts the problem all the way up to PSPACE-completeness.

Self-test recap

Recall One-line answers

∃ combines children with? ::: OR (true if at least one branch is true). ∀ combines children with? ::: AND (true only if both branches are true). Why is a formula with a free variable not in TQBF? ::: Its truth value depends on that variable; TQBF needs closed formulas. Space used by the recursive evaluator on $n$ vars? ::: $O (n \cdot ∣ ψ ∣)$ — one reused root-to-leaf path. Time used? ::: $Θ (2^{n})$ — it visits all leaves. Naïve $R_{t}$ size? ::: $Θ (2^{t})$ — exponential, reduction fails. Folded $R_{t}$ size? ::: $O (t)$ per your glue, polynomial overall — reduction works. What does $\forall (u, v)$ abbreviate? ::: Two nested universals $\forall u \forall v$ , one per pair coordinate. Truth of an alternating QBF as a game? ::: The ∃-player has a winning strategy.