Questions: Alternating Turing Machines and the Polynomial Hierarchy

Question 1

A problem is stated as: 'Does there exist a strategy for Player 1 such that for all responses by Player 2, Player 1 wins?' (Assume winning can be verified in polynomial time.) This problem most naturally belongs to:

• A. NP — it requires finding a winning strategy, which is an existential search problem
• B. co-NP — Player 2 is adversarial and universal, placing the problem in the co-NP class
• C. Σ₂ᵖ — it uses one existential quantifier followed by one universal quantifier
• D. PSPACE — all two-player games require polynomial space regardless of quantifier structure

Answer: (C)

The structure '∃ strategy such that ∀ responses, Player 1 wins' is exactly two alternating quantifiers: existential (∃) then universal (∀). In the polynomial hierarchy, Σ₂ᵖ is defined as the class with one existential quantifier followed by one universal quantifier — corresponding to an alternating machine that starts with an existential state and makes one switch to a universal mode. NP (Σ₁ᵖ) only uses one existential quantifier. The presence of the adversarial universal layer puts this firmly in Σ₂ᵖ, not NP. PSPACE would only apply if the number of quantifier alternations were unbounded.

Question 2

The class NP corresponds to alternating Turing machines using which configuration?

• A. Universal states only, with one quantifier alternation
• B. Existential states only, with one quantifier alternation (Σ₁ᵖ)
• C. Alternating ∃/∀ states with exactly one alternation
• D. Unrestricted alternations between ∃ and ∀ states, bounded by polynomial time

Answer: (B)

NP = Σ₁ᵖ is the class of problems solvable by an ATM that uses only existential states — equivalent to asking 'does there exist a branch of computation that accepts?' This is exactly what a nondeterministic Turing machine does: it guesses (existential choice) and accepts if any guess leads to acceptance. co-NP = Π₁ᵖ uses only universal states ('do all branches accept?'). Each additional level of the polynomial hierarchy adds exactly one more quantifier alternation, strictly increasing the machine's apparent power (assuming the hierarchy does not collapse).

Question 3

An alternating Turing machine operating in polynomial time with an unlimited (polynomial) number of quantifier alternations can decide exactly the problems in PSPACE.

• T. True
• F. False

Answer: True

This is the deep theorem APTIME = PSPACE. Intuitively, each quantifier alternation in the polynomial hierarchy adds one more 'round' of ∃/∀ reasoning. The polynomial hierarchy PH covers a fixed number of alternations (Σₖᵖ for finite k). PSPACE allows polynomially many alternations — an exponentially richer form of alternation. The equivalence APTIME = PSPACE shows that the power to alternate between existential and universal modes, even just in polynomial time, is equivalent to the power to use polynomial amounts of memory. This places PSPACE strictly above PH (assuming PH doesn't collapse) and below EXPTIME.

Question 4

A universal state in an alternating Turing machine accepts if at least one of its successor computation branches leads to acceptance.

• T. True
• F. False

Answer: False

That describes an existential state, not a universal state. In an alternating Turing machine, existential (∃) states accept if at least one successor branch accepts — corresponding to the prover's optimal choice. Universal (∀) states accept only if every successor branch accepts — corresponding to the adversary playing optimally against you. This distinction is the core of alternation: ∃ states model 'there exists a good move' (NP-style reasoning) while ∀ states model 'every possible response leads to my victory' (co-NP-style reasoning). Universal states are strictly harder to satisfy than existential states.

Question 5

Using the game-tree analogy for alternating Turing machines, explain why Σ₂ᵖ is considered harder than NP, and what the additional 'layer' requires of the machine.

Model answer: In the game-tree analogy, an existential state is your move — you just need one good choice to win. A universal state is your adversary's move — every possible response they make must still lead to your victory. NP (Σ₁ᵖ) corresponds to a game with only your move: 'does there exist a certificate that witnesses acceptance?' You just need one good guess. Σ₂ᵖ adds a universal layer: 'does there exist a strategy such that for all adversary responses, you still win?' Now you must not just find one good answer, but find a strategy that works against every possible counterattack. This is strictly harder because verifying a Σ₂ᵖ witness requires checking that it succeeds against all possible opponent responses — a co-NP-hard check — rather than just verifying a single certificate.

The hierarchy reflects a natural progression in the complexity of reasoning: NP = one ∃ round, Σ₂ᵖ = ∃ then ∀, Σ₃ᵖ = ∃∀∃, and so on. Each level assumes the lower levels are strictly easier (i.e., PH does not collapse). Problems like 'does a Boolean formula with alternating quantifiers have a satisfying assignment' are complete for each level, giving concrete natural examples of this quantifier-depth hierarchy.