Which of the following problems is most naturally at the Σ₂^P level of the polynomial hierarchy?
ADeciding if a Boolean formula is satisfiable (SAT)
BDeciding if a Boolean formula is a tautology (true for all assignments)
CDeciding if a Boolean formula has a minimal equivalent of size at most k
DDeciding if a graph has a Hamiltonian cycle
Minimal equivalent formula requires: (∃ small formula F') such that (∀ assignments x, F'(x) = F(x)). This ∃∀ quantifier alternation places it at Σ₂^P. SAT is Σ₁^P = NP (just ∃); tautology is Π₁^P = coNP (just ∀). The Σ₂^P level is the first that requires both quantifier types working together — neither an NP nor coNP oracle alone suffices.
Question 2 Multiple Choice
If it were proven that Σ₂^P = Π₂^P, what would be the correct conclusion?
AOnly the second and third levels of PH would collapse; higher levels remain separate
BThe entire polynomial hierarchy would collapse to the second level
CThe hierarchy would collapse to P, since Σ₂^P would then equal NP
DPSPACE would also collapse to Σ₂^P
If Σ₂^P = Π₂^P, then PH collapses entirely to Σ₂^P — every level above it equals Σ₂^P. Each level is built using the previous level as an oracle; if the second level collapses (is closed under complement), the third level can be simulated within the second, and the collapse propagates upward. However, this says nothing definitive about PSPACE, which could remain strictly larger.
Question 3 True / False
Σ₁^P = NP because NP problems are characterized by the existence of a polynomial-time verifiable certificate, which is exactly the existential quantifier ∃.
TTrue
FFalse
Answer: True
This is correct by definition. NP is the class of problems where a 'yes' answer has a witness (certificate) that can be verified in polynomial time. The existential quantifier ∃ in Σ₁^P captures exactly this structure. CoNP = Π₁^P uses the universal quantifier: 'for all candidates, the checker rejects' — capturing problems where 'no' instances must hold for all inputs.
Question 4 True / False
The polynomial hierarchy is contained in PSPACE because PSPACE can simulate any bounded number of quantifier alternations by exhaustive search within polynomial space.
TTrue
FFalse
Answer: True
PSPACE can simulate any finite number of alternating quantifiers: for each ∃ quantifier, try all witnesses; for each ∀ quantifier, verify all possibilities — reusing polynomial space across trials. Since each level of PH has a fixed finite number of quantifier alternations, PSPACE contains the entire hierarchy. It is widely believed but unproven that PSPACE is strictly larger than PH.
Question 5 Short Answer
Why does the polynomial hierarchy 'collapse to level i' if Σᵢ^P = Πᵢ^P, and why is this believed not to happen for any level i?
Think about your answer, then reveal below.
Model answer: Each level Σᵢ₊₁^P is defined as NP^(Σᵢ^P) — nondeterministic polynomial time with a Σᵢ^P oracle. If Σᵢ^P = Πᵢ^P (the level is closed under complement), then adding another quantifier alternation at level i+1 yields nothing new: the ∀ quantifier can be simulated within Σᵢ^P, so Σᵢ₊₁^P = Σᵢ^P. The argument propagates to all higher levels. Complexity theorists believe no collapse occurs because it would imply surprising consequences similar to P = NP — and because showing an assumption implies collapse of PH is widely taken as evidence against that assumption.
The collapse property makes PH useful as a complexity-theoretic barometer: it acts as a measure of plausibility. When a hypothesis implies PH collapses, that hypothesis is considered unlikely. The infinite hierarchy conjecture is one of the strongest structural beliefs in complexity theory, supported by the observation that every known result that would collapse PH is also believed to be false.