Question bank — PSPACE — Quantified Boolean Formula

True — every variable is quantified (no free variables), so there is nothing left to plug in; the formula denotes a fact, not a function.

True — an all-existential QBF asks "is there an assignment making $\varphi$ true?", which is exactly the SAT question. SAT is the all-$\exists$ slice of TQBF.

False — $\forall$ demands both $x=0$ and $x=1$ satisfy $\varphi$; "at least one" is the $\exists$ rule, not $\forall$.

True — unsatisfiable means no assignment works, so certainly not all assignments work; the all-$\forall$ formula fails on the first bad assignment.

False — you can guess the $\exists$ choices, but a $\forall$ asserts a property of all $2^k$ values; no single nondeterministic certificate captures that. TQBF is PSPACE-complete and not believed to be in NP.

False in general — in $\forall y\exists x$ the choice of $x$ may depend on $y$; swapping forces one fixed $x$ to work for all $y$. Example: $\forall y\exists x(x\ne y)$ over a domain of size $\ge 2$ is true, but $\exists x\forall y(x\ne y)$ is false.

True — like-quantifiers commute; both just say "there is a choice of the pair $(x,y)$ making $\varphi$ true", and order among two $\exists$'s carries no dependency.

False — that is the whole trick: it recurses on the first branch, keeps only the resulting bit b0, then reuses the same memory for the second branch. Space stays $O(n\cdot |\psi |)$ where $n$ = number of quantifiers, $|\psi |$ = formula size.

False — exponential time (the roughly $2^n$ leaves visited) does not imply exponential space. Memory is reused across branches, so space is polynomial; PSPACE bounds space, not time. See PSPACE and Polynomial Space.

True — NP $\subseteq$ PSPACE and TQBF is PSPACE-complete, so every PSPACE problem (hence every NP problem) reduces to it. See NP vs PSPACE.

Logically correct but the reduction is broken: recall ${\mathrm{REACH}}_t(a,b)$ means "$a$ reaches $b$ in $\le 2^t$ steps". Here ${\mathrm{REACH}}_{t-1}$ appears twice, so $|{\mathrm{REACH}}_t|\approx 2|{\mathrm{REACH}}_{t-1}|$ ⇒ size $2^{O(s)}$ — an exponential-size QBF, not a valid poly-time reduction. See Savitch's Theorem.

It is the heart of the fix: the $\forall (u,v)$ lets one copy of ${\mathrm{REACH}}_{t-1}$ stand for both halves $(a,m)$ and $(m,b)$, keeping size linear per level. Remove it and you're back to the exponential doubling.

Wrong — $x$ is quantified by the $\exists$, so there are no free variables; it is a closed QBF that evaluates to true.

Wrong — take $x=0$: then $x\wedge y=0\wedge y=0$ (the constant $0$) for every $y$, so the inner $\exists y$ fails. One failing $\forall$-branch makes the whole formula false.

Not always — $\exists$ is an OR; if $x=0$ already yields true (b0 = 1) you may stop early. (You test both only when the first branch is false.)

Wrong — completeness only says TQBF is a hardest PSPACE problem. Whether NP $=$ PSPACE is an open question; TQBF being complete doesn't settle it.

Because $\exists$ and $\forall$ alternate: the $\exists$-"Prover" wants the formula true, the $\forall$-"Spoiler" wants it false, and reading quantifiers left-to-right is exactly the sequence of moves. See Two-Player Games and Game Trees.

Truth requires that for every $\forall$-move there still exists an $\exists$-reply keeping $\varphi$ true — precisely the definition of a strategy that wins no matter what the opponent does.

Here $n$ counts quantifiers (= recursion depth) and $|\psi |$ is the formula size. It unrolls to $S(n)=O(n\cdot |\psi |)$ — a linear-in-depth sum, because each level adds only $O(|\psi |)$ overhead and the memory of a finished branch is freed before the next.

The $\forall (u,v)$ ranges over the two required configuration-pairs $(a,m)$ and $(m,b)$; a single guarded formula "$(u,v)$ is one of these $\Rightarrow {\mathrm{REACH}}_{t-1}(u,v)$" checks both while writing ${\mathrm{REACH}}_{t-1}$ once. This is Savitch's theorem as quantifiers. See Savitch's Theorem.

Alternation lets later choices depend on earlier ones (a strategy), encoding an adversary. Pure SAT has no adversary — just one existential search — which is why SAT is "only" NP-complete. See Polynomial Hierarchy.

The number of quantifiers $=$ recursion depth $=$ game length; polynomial depth keeps the reused memory polynomial. An exponentially long game would need exponential depth and break the bound.

True — pick $x=1$ (the constant true), giving value $1$. A lone $\exists$ needs just one satisfying value.

False — $x=0$ makes the body the constant $0$, and $\forall$ requires all values to work, so one failure suffices to kill it.

Valid — it's the base case with no variables left; EVAL just computes the Boolean value directly ($1\vee 0=1$, since $1$ is true), in polynomial space.

In prenex QBF each variable is bound once; re-quantifying is malformed. If forced by shadowing rules, the inner $\forall x$ rebinds $x$ and the outer $\exists x$ becomes vacuous — a degenerate case to avoid by renaming.

No — $\exists \exists$ and $\forall \forall$ commute freely; dependency only arises across an $\exists$–$\forall$ boundary, where order encodes who-chooses-after-whom.

No effect on truth — a $\forall$ over an unused variable is vacuous (both values give the same result), so it can be dropped without changing the answer.