Alternating Turing machine

Example

Perhaps the most natural problem for alternating machines to solve is the quantified Boolean formula problem, which is a generalization of the Boolean satisfiability problem in which each variable can be bound by either an existential or a universal quantifier. The alternating machine branches existentially to try all possible values of an existentially quantified variable and universally to try all possible values of a universally quantified variable, in the left-to-right order in which they are bound. After deciding a value for all quantified variables, the machine accepts if the resulting Boolean formula evaluates to true, and rejects if it evaluates to false. Thus at an existentially quantified variable the machine is accepting if a value can be substituted for the variable that renders the remaining problem satisfiable, and at a universally quantified variable the machine is accepting if any value can be substituted and the remaining problem is satisfiable.

Such a machine decides quantified Boolean formulas in time ${\displaystyle n^2}$ and space ${\displaystyle n}$.

The Boolean satisfiability problem can be viewed as the special case where all variables are existentially quantified, allowing ordinary nondeterminism, which uses only existential branching, to solve it efficiently.

Complexity classes and comparison to deterministic Turing machines

The following complexity classes are useful to define for ATMs:

• ${\displaystyle \mathsf{A}\mathsf{P}=\bigcup _{k>0}\mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(n^k)}$ are the languages decidable in polynomial time
• ${\displaystyle \mathsf{A}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}=\bigcup _{k>0}\mathsf{A}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(n^k)}$ are the languages decidable in polynomial space
• ${\displaystyle \mathsf{A}\mathsf{E}\mathsf{X}\mathsf{P}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}=\bigcup _{k>0}\mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(2^{n^k})}$ are the languages decidable in exponential time

These are similar to the definitions of P, PSPACE, and EXPTIME, considering the resources used by an ATM rather than a deterministic Turing machine. Chandra, Kozen, and Stockmeyer proved the theorems

• ALOGSPACE = P
• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE
• ${\displaystyle \mathsf{A}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(f(n))=\bigcup _{c>0}\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(2^{cf(n)})=\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(2^{O(f(n))})}$
• ${\displaystyle \mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(g(n))\subseteq \mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(g(n))}$
• ${\displaystyle \mathsf{N}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(g(n))\subseteq \bigcup _{c>0}\mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(c\times g(n{)}^2),}$

when ${\displaystyle f(n)\ge \log (n)}$ and ${\displaystyle g(n)\ge \log (n)}$.

A more general form of these relationships is expressed by the parallel computation thesis.

Bounded alternation

Definition

An alternating Turing machine with k alternations is an alternating Turing machine that switches from an existential to a universal state or vice versa no more than k−1 times. (It is an alternating Turing machine whose states are divided into k sets. The states in even-numbered sets are universal and the states in odd-numbered sets are existential (or vice versa). The machine has no transitions between a state in set i and a state in set j < i.)

${\displaystyle \mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(C,j)={\mathrm{\Sigma }}_j\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(C)}$ is the class of languages decidable in time ${\displaystyle f\in C}$ by a machine beginning in an existential state and alternating at most ${\displaystyle j-1}$ times. It is called the jth level of the ${\displaystyle \mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(C)}$ hierarchy.

${\displaystyle \mathsf{c}\mathsf{o}\mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(C,j)={\mathrm{\Pi }}_j\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(C)}$ is defined in the same way, but beginning in a universal state; it consists of the complements of the languages in ${\displaystyle \mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(f,j)}$.

${\displaystyle \mathsf{A}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(C,j)={\mathrm{\Sigma }}_j\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(C)}$ is defined similarly for space bounded computation.

Example

Consider the circuit minimization problem: given a circuit A computing a Boolean function f and a number n, determine if there is a circuit with at most n gates that computes the same function f. An alternating Turing machine, with one alternation, starting in an existential state, can solve this problem in polynomial time (by guessing a circuit B with at most n gates, then switching to a universal state, guessing an input, and checking that the output of B on that input matches the output of A on that input).

Collapsing classes

It is said that a hierarchy collapses to level j if every language in level ${\displaystyle k\ge j}$ of the hierarchy is in its level j.

As a corollary of the Immerman–Szelepcsényi theorem, the logarithmic space hierarchy collapses to its first level. As a corollary the ${\displaystyle \mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(f)}$ hierarchy collapses to its first level when ${\displaystyle f=\mathrm{\Omega }(\log )}$ is space constructible.

Special cases

An alternating Turing machine in polynomial time with k alternations, starting in an existential (respectively, universal) state can decide all the problems in the class ${\displaystyle {\mathrm{\Sigma }}_k^p}$ (respectively, ${\displaystyle {\mathrm{\Pi }}_k^p}$). These classes are sometimes denoted ${\displaystyle {\mathrm{\Sigma }}_k\mathrm{P}}$ and ${\displaystyle {\mathrm{\Pi }}_k\mathrm{P}}$, respectively. See the polynomial hierarchy article for details.

Another special case of time hierarchies is the logarithmic hierarchy.