An alternating Turing machine reaches a universal (∀) state and branches into three computation paths. Path 1 accepts, Path 2 accepts, and Path 3 rejects. What does the ATM do at this universal state?
AAccept — because a majority of branches (2 out of 3) accepted
BAccept — because at least one branch accepted
CReject — because a universal state requires ALL branches to accept, and one rejected
DThe behavior is undefined — the ATM must be deterministic at universal states
A universal (∀) state is the mirror image of an existential state. An existential state accepts if ANY branch accepts; a universal state accepts only if ALL branches accept. Since Path 3 rejected, the universal state rejects regardless of how many other branches accepted. This is the key distinction that makes alternation more expressive than simple nondeterminism. Universal states enforce 'for all' quantification — the machine must succeed on every possible branch, modeling adversarial or exhaustive verification.
Question 2 Multiple Choice
Which complexity class corresponds to polynomial-time ATMs that start in a universal (∀) state and alternate quantifiers exactly once (∀ then ∃)?
ANP — because alternation with polynomial time always gives NP
BΠ₂ᴾ — the class corresponding to ∀∃ quantifier alternation in the polynomial hierarchy
Cco-NP — because starting in a universal state is exactly the co-NP model
DPSPACE — because any alternation between ∃ and ∀ collapses to PSPACE
Σₖᴾ and Πₖᴾ correspond to ATMs starting existential (Σ) or universal (Π) and alternating k times. co-NP is Π₁ᴾ (universal only, no further alternation). NP is Σ₁ᴾ (existential only). A ∀∃ computation with one alternation is Π₂ᴾ. PSPACE equals APTIME — polynomial-space deterministic computation equals polynomial-time alternating computation — but a single alternation is far below that ceiling. The polynomial hierarchy is precisely indexed by the number of quantifier alternations.
Question 3 True / False
A standard nondeterministic Turing machine is equivalent to an alternating Turing machine in which all states are existential (∃) states.
TTrue
FFalse
Answer: True
True. A nondeterministic TM accepts if ANY branch of its computation tree reaches an accepting state — exactly the semantics of an existential state. An ATM with only ∃ states is indistinguishable from an NTM. Introducing ∀ states adds a second type of branching that NTMs lack. This is why NTMs capture NP (existential polynomial time), while ATMs with alternation between ∃ and ∀ capture the full polynomial hierarchy, one level per alternation.
Question 4 True / False
An alternating Turing machine accepts an input if any branch in its computation tree reaches an accepting state, regardless of whether that branch passed through universal states.
TTrue
FFalse
Answer: False
False. Acceptance in an ATM is not determined by any single branch — it is evaluated bottom-up on the computation tree, respecting the semantics of each state type. An existential node is accepting if at least one child subtree is accepting; a universal node is accepting only if all child subtrees are accepting. The overall result is determined by recursively applying these rules from the leaves to the root. A computation reaching an accept leaf via a path through a universal state where another branch rejected still causes rejection at that universal state.
Question 5 Short Answer
State the theorem ATIME(f(n)) = DSPACE(f(n)) and explain intuitively why alternating time equals deterministic space.
Think about your answer, then reveal below.
Model answer: ATIME(f(n)) = DSPACE(f(n)): the problems solvable by an alternating TM in f(n) time equal those solvable by a deterministic TM in f(n) space. Intuitively, alternation lets a machine branch into exponentially many paths by choosing ∃ or ∀ at each step — effectively exploring a computation tree of exponential size in linear time. Deterministic space achieves the same exponential exploration by reusing space: it can revisit exponentially many configurations within f(n) memory by running one path at a time. Both resources trade off the same exponential exploration capability.
Key consequences include ALOGSPACE = P (alternating log-space equals deterministic polynomial time) and APTIME = PSPACE (alternating polynomial time equals deterministic polynomial space). These results reveal deep structural connections between time and space complexity that are invisible in the standard TM model. ATMs provide the conceptual bridge: they show that adding alternation to a time-bounded model is equivalent to upgrading to a space-bounded model, which explains why complexity class hierarchies have structural parallels and why the polynomial hierarchy lies inside PSPACE.