PSPACE — Quantified Boolean Formula — Hinglish notes

4.6.28 · Coding › Theory of Computation

QBF EVALUATE KAISE KAREIN — recursive algorithm scratch se derive karo

Hum chahte hain ek algorithm EVAL(ψ) jo truth value return kare. Isse leading quantifier ke meaning se banao.

Base case. Agar $ψ$ mein koi quantifier nahi hai, toh yeh ek closed Boolean expression hai jisme saare variables fixed hain → bas plug in karo aur compute karo. Cost: polynomial space.

Existential step. $ψ = \exists x ψ^{'}$ . Definition ke anusaar $\exists x ψ^{'}$ true hai iff $ψ^{'}$ $x = 0$ ke liye YA $x = 1$ ke liye true hai: $EVAL (\exists x ψ^{'}) = EVAL (ψ^{'} [x = 0]) \lor EVAL (ψ^{'} [x = 1]) .$

Universal step. $ψ = \forall x ψ^{'}$ true hai iff $ψ^{'}$ dono values ke liye hold kare: $EVAL (\forall x ψ^{'}) = EVAL (ψ^{'} [x = 0]) \land EVAL (ψ^{'} [x = 1]) .$

TQBF PSPACE-COMPLETE KYO HAI (sketch jo tum reconstruct kar sako)

Intuition Do directions

(1) PSPACE mein: upar wala recursive evaluator $O (n \cdot ∣ ψ ∣)$ space use karta hai. ✔

(2) PSPACE-hard: Koi bhi language $L \in PSPACE$ lo jo space $s = n^{k}$ mein decide ho. Uska configuration graph $\leq 2^{O (s)}$ nodes ka hai. Acceptance = "kya $c_{start}$ se $c_{accept}$ tak koi path hai?" Hum "config $a$ config $b$ tak $\leq 2^{t}$ steps mein pahunchti hai" ko ek QBF $REACH_{t} (a, b)$ se encode karte hain.

Naive tarike se $REACH_{t} = \exists m [REACH_{t - 1} (a, m) \land REACH_{t - 1} (m, b)]$ formula ko har level par double karta hai (→ exponential size). Trick (Savitch-style) ek $\forall$ use karke dono halves ko fold karti hai: $REACH_{t} (a, b) = \exists m \forall (u, v) [((u, v) = (a, m) \lor (u, v) = (m, b)) \Rightarrow REACH_{t - 1} (u, v)] .$ Ab $REACH_{t - 1}$ ek baar aata hai, toh size $t = O (s)$ levels par $O (s)$ se badhti hai → polynomial-size QBF. Yeh $\forall$ -folding proof ka dil hai — aur yeh literally Savitch's theorem hai quantifiers ke roop mein expressed.

80/20 — actually kya yaad rakhna hai

Flashcards

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

Ek single truth value — true ya false.

SAT is which special case of TQBF?

Saare quantifiers existential:

\exists x_{1} \dots \exists x_{n} ϕ

How is

\exists x ψ^{'}

evaluated recursively?

EVAL (ψ^{'} [x = 0]) \lor EVAL (ψ^{'} [x = 1])

How is

\forall x ψ^{'}

evaluated recursively?

EVAL (ψ^{'} [x = 0]) \land EVAL (ψ^{'} [x = 1])

Why is TQBF in PSPACE despite exponential time?

Recursion dono branches mein same memory reuse karta hai; space

= O (n \cdot ∣ ψ ∣)

What is TQBF's complexity-class status?

PSPACE-complete (PSPACE ka canonical complete problem).

In the PSPACE-hardness reduction, why add

\forall (u, v)

REACH_{t}

REACH_{t - 1}

sirf ek baar aaye → polynomial-size formula (Savitch folding).

What goes wrong with

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

R_{t - 1}

do baar aata hai → formula size har level par double hoti hai → exponential reduction.

Game interpretation of a true QBF?

\exists

-player ke paas

\forall

-player ke against winning strategy hai.

Why isn't

\exists x \forall y ϕ = \forall y \exists x ϕ

\forall y \exists x

mein,

x

y

par depend kar sakta hai; swap karne se ek

x

sabhi

y

ke liye force ho jata hai.

Recall Feynman: ek 12-saal ke bacche ko samjhao

Socho ek tug-of-war switches ke saath khela ja raha hai. Player YES chahta hai bulb ON rahe; player NO chahta hai OFF rahe. Woh ek fixed order mein baari-baari switches flip karte hain. Chhota word "exists" matlab YES ki baari hai — YES ko sirf ek acchi flip chahiye. "for all" matlab NO ki baari hai, aur YES tabhi jitega jab bulb chahe NO kuch bhi kare ON rahe. Sawaal "kya yeh QBF true hai?" bas poochta hai: kya YES hamesha yeh game jeet sakta hai? Check karne ke liye computer har possible game khelkar dekhta hai — lekin chalaki se wahi scratch paper erase karke reuse karta hai har branch ke liye, toh use zyada paper nahi chahiye (= kam memory), chahe bahut time lage.

Connections

SAT and NP-completeness — TQBF, SAT ka PSPACE analogue hai.
Savitch's Theorem — $\forall$ -folding trick quantifiers ke roop mein reuse hoti hai.
PSPACE and Polynomial Space — class jiske liye TQBF complete hai.
Polynomial Hierarchy — bounded-alternation QBF levels $Σ_{k}, Π_{k}$ deta hai.
Two-Player Games and Game Trees — QBF as a perfect-information game.
NP vs PSPACE — kyun TQBF NP mein nahi maana jata.

PSPACE — Quantified Boolean Formula

YEH HAI KYA

QBF EK GAME KYO HAI

QBF EVALUATE KAISE KAREIN — recursive algorithm scratch se derive karo

TQBF PSPACE-COMPLETE KYO HAI (sketch jo tum reconstruct kar sako)

80/20 — actually kya yaad rakhna hai

Flashcards

Connections

Concept Map