SAT asks whether there exists an assignment making a Boolean formula true. TQBF (True Quantified Boolean Formula) asks whether a fully quantified formula with alternating ∃ and ∀ quantifiers is true. Why is TQBF believed to be strictly harder than SAT?
ATQBF formulas are exponentially longer than SAT instances, requiring more memory to store
BTQBF requires reasoning about all possible assignments to universally-quantified variables — you must account for every adversarial choice, not just find one satisfying assignment
CTQBF can only be solved by exhaustive search, while SAT has efficient heuristics like DPLL
DTQBF is in a higher complexity class than PSPACE, placing it beyond the reach of polynomial-space algorithms
SAT is an existential question: find one assignment that works. A lucky guess can be verified in polynomial time (NP). TQBF adds universal quantifiers: for every assignment to some variables, there must exist an assignment to others that satisfies the formula. You cannot just 'find a witness' — you must reason about all possible adversarial choices, which cannot be verified by a single assignment. This ∃∀ alternation is what places TQBF in PSPACE-complete rather than NP-complete. TQBF is still solvable in polynomial space (Savitch's theorem), not beyond PSPACE.
Question 2 Multiple Choice
A researcher claims that determining 'Can Player A force a win from this board position in generalized chess on an n×n board?' is naturally PSPACE-complete. Which feature of the problem makes this the case?
AChess has exponentially many possible board positions, which requires exponential memory to enumerate
BChess is a deterministic game with no randomness, which automatically implies PSPACE-completeness
CMoves alternate between existential (Player A choosing) and universal (Player B responding) choices, mapping directly to the ∃∀ quantifier alternation in TQBF
DNo known polynomial-time algorithm exists for chess, placing it in PSPACE by definition
'Can A force a win?' expands as: ∃(A's move₁) ∀(B's response) ∃(A's move₂) ∀(B's response) ... → winning position. Each of A's choices is existential (A picks the best move), each of B's choices is universal (B plays optimally against A). This alternating quantifier structure is precisely TQBF's structure. Game-solving hardness comes not from having many positions, but from the adversarial alternation — you must plan against all possible opponent strategies, not just find a single winning path.
Question 3 True / False
PSPACE-complete problems require exponential space to solve, making them fundamentally more resource-intensive than NP-complete problems.
TTrue
FFalse
Answer: False
This is the defining misconception. PSPACE-complete problems are, by definition, in PSPACE — they CAN be solved using only polynomial space. That is precisely what 'PSPACE' means: the class of problems solvable within polynomial space. What may be exponential is the TIME required, but not the space. NP-complete problems are also in PSPACE (NP ⊆ PSPACE), so they too can be solved in polynomial space. PSPACE-completeness indicates harder-than-NP hardness in terms of likely time complexity, but it says nothing about exponential space requirements.
Question 4 True / False
Every NP-complete problem can be reduced in polynomial time to any PSPACE-complete problem, meaning PSPACE-hard problems are at least as hard as NP-hard problems under standard complexity assumptions.
TTrue
FFalse
Answer: True
NP ⊆ PSPACE, so every NP problem (including every NP-complete problem) is also in PSPACE. By the definition of PSPACE-completeness, every problem in PSPACE polynomial-time reduces to any PSPACE-complete problem. Since NP-complete problems are in PSPACE, they reduce to PSPACE-complete problems. Combined with the widespread belief that P ≠ NP ≠ PSPACE, PSPACE-complete problems are believed to be strictly harder than NP-complete ones — but not by virtue of needing more space, rather by needing (apparently) more time.
Question 5 Short Answer
Explain why alternating quantifiers (∃∀) in TQBF capture something fundamentally harder than the single existential quantifier (∃) in SAT, and connect this to the intuition from two-player games.
Think about your answer, then reveal below.
Model answer: SAT with a single ∃ quantifier asks: is there at least one assignment that works? A single 'witness' — one satisfying assignment — is sufficient to prove the answer is yes, and can be checked in polynomial time. TQBF with alternating ∃∀ quantifiers asks: does there exist a strategy that works against every possible adversarial choice? You cannot just produce one assignment; you need a complete strategy tree covering all branches of the ∀ quantifier. In game terms: SAT is 'can I find one winning move?' (solvable with a lucky guess + verification), while TQBF is 'can I force a win regardless of what my opponent does?' (requires evaluating all of the opponent's responses at every turn).
The depth of quantifier alternation directly corresponds to the number of game rounds. TQBF with k alternating quantifier blocks corresponds to a k-round game. As the game length grows (more quantifier alternations), the problem requires evaluating an exponentially large game tree — but the key insight is that this tree can be evaluated in polynomial SPACE using recursive Savitch-style computation, trading time for space.