PSPACE — Quantified Boolean Formula — Coding notes

HOW to evaluate a QBF — derive the recursive algorithm from scratch

We want an algorithm EVAL(ψ) returning the truth value. Build it from the meaning of the leading quantifier.

Base case. If $\psi$ has no quantifiers, it's a closed Boolean expression with all variables fixed → just plug in and compute. Cost: polynomial space.

Existential step. $\psi = \exists x\, \psi'$ . By definition $\exists x\,\psi'$ is true iff $\psi'$ is true for $x{=}0$ OR $x{=}1$ : $\mathrm{EVAL}(\exists x\,\psi') = \mathrm{EVAL}(\psi'[x{=}0]) \;\lor\; \mathrm{EVAL}(\psi'[x{=}1]).$

Universal step. $\psi = \forall x\,\psi'$ is true iff $\psi'$ holds for both values: $\mathrm{EVAL}(\forall x\,\psi') = \mathrm{EVAL}(\psi'[x{=}0]) \;\land\; \mathrm{EVAL}(\psi'[x{=}1]).$

WHY TQBF is PSPACE-complete (sketch you can reconstruct)

Intuition Two directions

(1) In PSPACE: the recursive evaluator above uses $O(n\cdot|\psi|)$ space. ✔

(2) PSPACE-hard: Take any language $L\in\mathrm{PSPACE}$ decided in space $s=n^k$ . Its configuration graph has $\le 2^{O(s)}$ nodes. Acceptance = "is there a path from $c_{\text{start}}$ to $c_{\text{accept}}$ ?" We encode "config $a$ reaches config $b$ in $\le 2^t$ steps" as a QBF $\mathrm{REACH}_t(a,b)$ .

Naïvely $\mathrm{REACH}_t = \exists m\,[\mathrm{REACH}_{t-1}(a,m)\land \mathrm{REACH}_{t-1}(m,b)]$ doubles the formula each level (→ exponential size). The trick (Savitch-style) uses a $\forall$ to fold the two halves into one: $\mathrm{REACH}_t(a,b)=\exists m\,\forall (u,v)\,\big[((u,v){=}(a,m)\lor (u,v){=}(m,b))\Rightarrow \mathrm{REACH}_{t-1}(u,v)\big].$ Now $\mathrm{REACH}_{t-1}$ appears once, so size grows by $O(s)$ per level over $t=O(s)$ levels → polynomial-size QBF. This $\forall$ -folding is the heart of the proof — and it's literally Savitch's theorem expressed as quantifiers.

The 80/20 — what to actually remember

Flashcards

What does a fully-quantified Boolean formula evaluate to (no free vars)?

A single truth value — true or false.

SAT is which special case of TQBF?

All quantifiers existential:

\exists x_1\cdots\exists x_n\,\phi

How is

\exists x\,\psi'

evaluated recursively?

\mathrm{EVAL}(\psi'[x{=}0]) \lor \mathrm{EVAL}(\psi'[x{=}1])

How is

\forall x\,\psi'

evaluated recursively?

\mathrm{EVAL}(\psi'[x{=}0]) \land \mathrm{EVAL}(\psi'[x{=}1])

Why is TQBF in PSPACE despite exponential time?

Recursion reuses the same memory across the two branches; space

=O(n\cdot|\psi|)

What is TQBF's complexity-class status?

PSPACE-complete (canonical complete problem for PSPACE).

In the PSPACE-hardness reduction, why add

\forall(u,v)

\mathrm{REACH}_t

To make

\mathrm{REACH}_{t-1}

appear only once → polynomial-size formula (Savitch folding).

What goes wrong with

\exists m[R(a,m)\land R(m,b)]

R_{t-1}

appears twice → formula size doubles each level → exponential reduction.

Game interpretation of a true QBF?

The

\exists

-player has a winning strategy against the

\forall

-player.

Why isn't

\exists x\forall y\,\phi = \forall y\exists x\,\phi

\forall y\exists x

x

may depend on

y

; swapping forces one

x

for all

y

Recall Feynman: explain to a 12-year-old

Imagine a tug-of-war played with switches. Player YES wants a light bulb ON; player NO wants it OFF. They take turns flipping switches in a fixed order. The little word "exists" means it's YES's turn — YES only needs one good flip. The word "for all" means it's NO's turn, and YES wins only if the bulb stays ON no matter what NO does. The question "is this QBF true?" just asks: can YES always win this game? To check, a computer plays out every possible game — but cleverly erases and reuses the same scratch paper for each branch, so it never needs much paper (= little memory), even though it may take a very long time.

Connections

SAT and NP-completeness — TQBF is the PSPACE analogue of SAT.
Savitch's Theorem — the $\forall$ -folding trick reused as quantifiers.
PSPACE and Polynomial Space — class TQBF is complete for.
Polynomial Hierarchy — bounded-alternation QBF gives levels $\Sigma_k, \Pi_k$ .
Two-Player Games and Game Trees — QBF as a perfect-information game.
NP vs PSPACE — why TQBF is unlikely to be in NP.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, normal SAT problem poochta hai: "kya koi assignment exist karta hai jo formula ko true bana de?" — yaani sirf ek ∃ (exists) player jo formula ko TRUE karna chahta hai. QBF (Quantified Boolean Formula) mein hum ∃ aur ∀ (for all) ko alternate karte hain, jaise do players ka game ho: ∃ = "Prover" jo TRUE chahta hai, ∀ = "Spoiler" jo FALSE chahta hai. Saari variables quantified hoti hain, koi free variable nahi, isliye QBF ka answer sidha true ya false hota hai.

Evaluate kaise karein? Simple recursion: $\exists x$ matlab dono values ( $x{=}0$ aur $x{=}1$ ) ka OR lo (ek bhi true mil gaya to kaam ho gaya). $\forall x$ matlab dono ka AND lo (saare true hone chahiye). Yeh ek game-tree ban jaata hai. Sabse important baat: jab hum tree explore karte hain, ek branch ka answer nikaalo, phir wahi memory dobara use karke doosri branch nikaalo — dono ko ek saath yaad rakhne ki zarurat nahi. Isliye space sirf $O(n\cdot|\psi|)$ lagta hai, time chahe exponential ho. Yahi reason hai ki TQBF, PSPACE mein hai.

Aur TQBF PSPACE-complete hai — matlab jaise SAT, NP ka "boss problem" hai, waise hi TQBF, PSPACE ka boss problem hai. Hardness ka proof Savitch wale trick se aata hai: reachability ko "config $a$ se $b$ tak $2^t$ steps mein pahunch sakte hain?" ke roop mein QBF banao. Agar tum naive tareeke se $\exists m[R(a,m)\land R(m,b)]$ likhoge to formula har level pe double ho jaayega (exponential size — galat!). Isliye ek extra $\forall(u,v)$ daal kar dono halves ko fold karte hain taaki $R_{t-1}$ sirf ek baar aaye — formula polynomial size ka reh jaata hai. Yaad rakho: "∃ = OR, ∀ = AND" aur "∀ se fold karo warna size phat jayega."

PSPACE — Quantified Boolean Formula

WHAT it is

WHY a QBF is a game

HOW to evaluate a QBF — derive the recursive algorithm from scratch

WHY TQBF is PSPACE-complete (sketch you can reconstruct)

The 80/20 — what to actually remember

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections