Alternation

Abstract

We define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate. Alternation links up time and space complexities rather well, in that alternating polynomial time equals deterministic polynomial space, and alternating linear space equals deterministic exponential time. Such considerations lead to a two-person game complete in polynomial time, and other games complete in exponential time. We also find that computability on a parallel processing machine is a rather rugged notion, and present two parallel processing models that are polynomially equivalent in their running times. We also show that while n-state alternating finite automata accept only regular sets that can be accepted by 22n-O(logn) state deterministic automata, alternating pushdown automata accept all languages accepted by Turing machines in deterministic exponential time.