Questions: Alternating Turing Machines

Question 1

A language L is in Σ₂P. Which description best characterizes the ATM that decides L in polynomial time?

• A. An ATM with only existential states, running in polynomial time — identical to NP
• B. An ATM that starts in an existential state, makes exactly one alternation to universal states, and runs in polynomial time
• C. An ATM with only universal states, which must verify all paths accept — the complement of NP
• D. An ATM that alternates between existential and universal states polynomially many times

Answer: (B)

Σ₂P corresponds to languages decidable by an ATM that begins with existential states (one block of ∃ quantifiers), then switches to universal states (one block of ∀ quantifiers), all within polynomial time. The subscript 2 counts the number of quantifier alternation blocks, and Σ indicates the leading quantifier is existential. NP is Σ₁P (existential only); Π₂P would start universally. Each additional alternation block adds another level to the polynomial hierarchy.

Question 2

What is the relationship between AP (the class of languages decided by polynomial-time ATMs) and the major complexity classes PSPACE and NP?

• A. AP = NP, because both allow branching over polynomial computations
• B. AP ⊂ PSPACE strictly, since alternation adds power beyond deterministic space
• C. AP = PSPACE, meaning polynomial-time alternating computation equals polynomial-space deterministic computation
• D. AP = EXP, because exploring all universal branches requires exponential resources

Answer: (C)

The fundamental theorem is AP = PSPACE: a language can be decided by a polynomial-time ATM if and only if it can be decided by a deterministic polynomial-space machine. Intuitively, alternation allows an ATM to simulate game trees — the universal quantifier plays the role of an adversary and the existential quantifier plays the role of a solver. PSPACE is exactly the class of languages where such two-player perfect-information games can be decided. This equality also implies ALOGSPACE = P, another striking equivalence.

Question 3

At a universal (∀) state, an alternating Turing machine accepts if and only if every branch of its computation from that state eventually leads to acceptance.

• T. True
• F. False

Answer: True

This is the defining rule for universal states. Unlike ordinary NTM states (or ATM existential states) where acceptance of any single branch suffices, a universal state requires all branches to lead to acceptance. If even one branch from a universal state ultimately rejects, the ATM rejects from that state. This mirrors universal quantification: 'for all y, the property holds.' Existential and universal states can be interleaved, capturing the nested quantifier structure of the polynomial hierarchy.

Question 4

ALOGSPACE equals NL (nondeterministic logspace) because both models compute with logspace bounds and involve nondeterministic branching.

• T. True
• F. False

Answer: False

ALOGSPACE = P, not NL. This is a striking result: adding universal states to a logspace machine jumps all the way up to deterministic polynomial time, not just to the nondeterministic version. NL is the class of languages decidable by nondeterministic logspace machines (without universal states), and NL ⊆ P. Alternation amplifies power dramatically: ALOGSPACE = P shows that alternation between ∃ and ∀ in logarithmic space captures all of polynomial-time computation.

Question 5

Explain how alternating between existential and universal states in an ATM captures the structure of nested quantifiers, and what complexity class is captured by polynomial-time ATMs.

Model answer: At an existential (∃) state, the ATM branches and accepts if any branch accepts — modeling 'there exists a choice that works.' At a universal (∀) state, the ATM accepts only if all branches accept — modeling 'every possible challenge is handled.' By interleaving these states, an ATM can decide properties of the form '∃x ∀y ∃z φ(x,y,z),' matching the nested quantifier prefix exactly. The number of alternations and the leading quantifier type determine which level of the polynomial hierarchy the language falls in. Polynomial-time ATMs with all possible alternations capture exactly PSPACE.

This quantifier-based view unifies complexity theory: Σₖ P (ATM starting ∃, k−1 alternations) and Πₖ P (starting ∀, k−1 alternations) together form the polynomial hierarchy PH, and PH ⊆ PSPACE. The theorem AP = PSPACE shows that allowing unrestricted alternation collapses the entire hierarchy into the single class PSPACE — a deep connection between quantifier complexity and space complexity. The ATM framework is one of the most compact tools for characterizing the polynomial hierarchy.