Foundations — PSPACE — Quantified Boolean Formula

Before you can read a single line of the parent note the TQBF topic, you need a pile of small symbols. This page defines every one of them from nothing — plain words, a picture, and the reason the topic needs it. Read top to bottom; each block uses only what came before it.

1. A Boolean variable — the atom

Picture it. A light switch. Up = $1$, down = $0$. Nothing in between.

Why the topic needs it. Every formula in this chapter is built out of these switches. When the parent note says "assignment," it means choosing an up/down position for every switch. With $n$ switches there are $2^n$ possible arrangements — that explosion is the whole reason the topic cares about time vs. space.

2. The connectives $\wedge ,\vee ,\neg$ — wiring the switches together

Picture it. Think of water pipes with valves.

• $\wedge$ = two valves in series: water flows only if both are open.
• $\vee$ = two valves in parallel: water flows if either is open.

Why the topic needs it. The inner formula $\varphi$ in a QBF is just switches wired with these three operations. The recursive evaluator in the parent note leans on one fact you can now see in the picture: for OR, one open valve already lets water through (so $\exists$ can stop early); for AND, one closed valve blocks everything (so $\forall$ can fail early).

3. A Boolean formula $\varphi$ and the arrow $\leftrightarrow$

Two more shorthands the parent uses:

• $a\to b$ ("$a$ implies $b$") is false only when $a=1$ and $b=0$; it equals $\neg a\vee b$.
• $a\leftrightarrow b$ ("$a$ iff $b$") is $1$ when $a$ and $b$ are equal.

Why the topic needs it. The worked examples in the parent ($x\vee y$, $x\leftrightarrow y$, $x\wedge y$) are exactly these tiny $\varphi$'s. And SAT is nothing but the question "can we make some $\varphi$ equal $1$?"

4. Free vs. bound variables — why a QBF has no inputs left

Picture it. $\varphi (x)=x\vee 0$ still has a blank $x$; you can't say if it's "true" until someone fills it. That $x$ is free.

Why the topic needs it. A QBF puts a quantifier in front of every variable, so no blanks remain. That is why the parent can say a QBF "is either true or false" — there is nothing left to plug in. Keep this: quantified = no free variables = a definite truth value.

5. The quantifiers $\exists$ and $\forall$ — the two players

Here $\psi [x=0]$ means "the formula $\psi$ with every $x$ replaced by $0$."

Picture it as players. Read left to right as turns in a game:

• at an $\exists x$, the Prover chooses $x$ to help make $\varphi$ true;
• at a $\forall x$, the Spoiler chooses $x$ to try to break it.

Why the topic needs it. This is the whole subject. Alternating $\exists /\forall$ is what separates TQBF from SAT (all-$\exists$), and it is the bridge to game trees and the polynomial hierarchy (which counts alternations).

6. Prenex form and the string $Q_1{x}_1\cdots Q_n{x}_n\varphi$

Picture it. A line of players queued up ($Q_1$ moves first), each grabbing one switch $x_i$, and only at the very end does the wired circuit $\varphi$ light up or stay dark.

Why the topic needs it. Reading the queue left-to-right is the recursive algorithm: peel off $Q_1$, branch on its two switch values, recurse on the rest.

7. The set-builder $\{\cdot :\cdot \}$ and the language TQBF

Why the topic needs it. "Is $\psi \in \mathrm{TQBF}$?" is the precise yes/no problem the whole chapter solves. Phrasing it as a language is what lets us compare it to SAT and place it in a complexity class.

8. Complexity classes: SPACE, PSPACE, and $2^n$

Why the topic needs it. "TQBF is PSPACE-complete" means (a) it lives in this class and (b) every PSPACE problem reduces to it. The reused-memory recursion gives (a); Savitch's theorem's $\forall$-folding gives (b). Where NP sits relative to all this is its own open question.

Prerequisite map

Equipment checklist

Test yourself — cover the right side and answer before revealing.