Favorite Theorems: Alternation

Introduction

Physicists continue to grapple over the relationship of time and space. In computational complexity we settled that question three decades ago: Space is just alternating time.

Chandra, Kozen and Stockmeyer, Alternation, JACM 1981. Based on two 1976 FOCS papers.

An alternating Turing machine is a nondeterministic machine with states marked either existential or universal. Consider a game where player 1 chooses the next legal configuration from existential states and player 2 chooses the next legal configuration from the universal states and player 1 wins if the machine halts in an accept state. The machine accepts those inputs where player 1 has a winning strategy.

Chandra, Kozen and Stockmeyer show

• ATIME(t(n)) ⊆ DSPACE(t(n)) ⊆ NSPACE(t(n)) ⊆ ATIME(t²(n))
• ASPACE(s(n)) = ∪_cDTIME(c^s(n))

Alternation causes a shift in the time-space hierarchy of classes: P = AL, PSPACE = AP, EXP = APSPACE, EXPSPACE = AEXP, etc. More importantly the two fundamental resource bounds of time and space are really just the same concept on different models.

Alternation allows us to show the PSPACE-completeness of many game-based problems. Also alternating machines set the stage for interactive proof systems which led to probabilistically checkable proofs, perhaps the most productive line of research in complexity over the past fifteen years.

The paper also characterizes the polynomial-time hierarchy using bounded alternation and shows that alternating finite automata still accept just regular languages (with a double-exponential blow-up in the number of states).