P36 · TQBF game tree

🔊 Listen

1 · TQBF and the game-tree interpretation

TQBF = {⟨φ⟩ : φ is a true quantified Boolean formula}. A QBF is a Boolean formula prefixed by alternating quantifiers ∃x₁ ∀x₂ ∃x₃ … followed by a quantifier-free Boolean kernel.

Recursive evaluation

∃x. ψ(x) is true iff ψ(0) is true OR ψ(1) is true.

∀x. ψ(x) is true iff ψ(0) is true AND ψ(1) is true.

Recurse until all quantifiers are stripped, then evaluate the propositional kernel.

The game interpretation

Think of TQBF as a game between two players. Player ∃ picks values for the ∃-bound variables, trying to make the kernel true. Player ∀ picks values for ∀-bound variables, trying to make it false. The formula is true iff ∃ has a winning strategy. This is why TQBF captures generalised game theory.

TQBF is PSPACE-complete (Sipser Theorem 8.9). The depth-first evaluation uses O(n) space — only the current path's partial assignment needs storage. Total tree has 2ⁿ leaves but the space is polynomial because each branch is computed independently and discarded.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

The quantifier order matters. ∃x ∀y. ψ(x, y) is generally not equivalent to ∀y ∃x. ψ(x, y). The first lets x be fixed; the second lets x depend on y.
"True QBF" means the formula evaluates to true under standard logical semantics. Not "there exists an assignment making it true" — quantifiers are part of the formula.
Space stays polynomial because of depth-first reuse. If you tried breadth-first (storing all 2ⁿ leaves), space would explode. DFS is essential.

🔊 Listen

4 · Q&A defence notes

Q1. Why is TQBF PSPACE-complete and not just NP-complete?
SAT has only existential quantification (one quantifier alternation). TQBF allows ∀∃∀∃… — unbounded alternation. Each alternation is an additional level of "guess and check" that NP can't handle but PSPACE can via its space-bounded computation.
Q2. How does the recursion use polynomial space?
Depth-first evaluation reuses memory at each level. Only the current path's partial assignment (one bit per variable) plus a stack frame per level is stored. Total: O(n) space.
Q3. Total tree size?
2ⁿ leaves and 2ⁿ⁺¹ − 1 internal nodes. Evaluating takes 2ⁿ time in the worst case. PSPACE-completeness shows no asymptotically faster algorithm is known, and is unlikely without major collapse.
Q4. What games does TQBF capture?
Any finite two-player game with alternating moves: generalised geography, generalised chess (on n×n boards), Go, FORMULA-GAME. All are PSPACE-complete or harder.

🔊 Listen

5 · Where to read more

Sipser: Theorem 8.9 (TQBF is PSPACE-complete). Lecture notes: Module 6 slides 2–3. Companion problems: P37 (TQBF3), P38 (geography), P39 (TQBF → geography), P40 (chess).