This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(May 2011) (Learn how and when to remove this message)

Incomputational complexity theory, analternating Turing machine (ATM) is anon-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of thecomplexity classesNP andco-NP. The concept of an ATM was set forth byChandra andStockmeyer^[1] and independently byKozen^[2] in 1976, with a joint journal publication in 1981.^[3]

The definition of NP uses theexistential mode of computation: ifany choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses theuniversal mode of computation: only ifall choices lead to an accepting state does the whole computation accept. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes.

Analternating Turing machine is anon-deterministic Turing machine whose states are divided into two sets:existential states anduniversal states. An existential state is accepting if some transition leads to an accepting state; a universal state is accepting if every transition leads to an accepting state. (Thus a universal state with no transitions accepts unconditionally; an existential state with no transitions rejects unconditionally). The machine as a whole accepts if the initial state is accepting.

Formally, a (one-tape)alternating Turing machine is a 5-tuple${\displaystyle M=(Q,\mathrm{\Gamma },\delta ,q_0,g)}$ where

• ${\displaystyle Q}$ is the finite set of states
• ${\displaystyle \mathrm{\Gamma }}$ is the finite tape alphabet
• ${\displaystyle \delta :Q\times \mathrm{\Gamma }\to \mathcal{P}(Q\times \mathrm{\Gamma }\times \{L,R\})}$ is called the transition function (L shifts the head left andR shifts the head right)
• ${\displaystyle q_0\in Q}$ is the initial state
• ${\displaystyle g:Q\to \{\wedge ,\vee ,accept,reject\}}$ specifies the type of each state

IfM is in a state${\displaystyle q\in Q}$ with${\displaystyle g(q)=accept}$ then that configuration is said to beaccepting, and if${\displaystyle g(q)=reject}$ the configuration is said to berejecting. A configuration with${\displaystyle g(q)=\wedge }$ is said to be accepting if all configurations reachable in one step are accepting, and rejecting if some configuration reachable in one step is rejecting. A configuration with${\displaystyle g(q)=\vee }$ is said to be accepting when there exists some configuration reachable in one step that is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in a classical NTM except the final state).M is said to accept an input stringw if the initial configuration ofM (the state ofM is${\displaystyle q_0}$, the head is at the left end of the tape, and the tape containsw) is accepting, and to reject if the initial configuration is rejecting.

Note that it is impossible for a configuration to be both accepting and rejecting, however, some configurations may be neither accepting or rejecting, due to the possibility of nonterminating computations.

When deciding if a configuration of an ATM is accepting or rejecting using the above definition, it is not always necessary to examine all configurations reachable from the current configuration. In particular, an existential configuration can be labelled as accepting if any successor configuration is found to be accepting, and a universal configuration can be labelled as rejecting if any successor configuration is found to be rejecting.

An ATM decides aformal language in time${\displaystyle t(n)}$ if, on any input of lengthn, examining configurations only up to${\displaystyle t(n)}$ steps is sufficient to label the initial configuration as accepting or rejecting. An ATM decides a language in space${\displaystyle s(n)}$ if examining configurations that do not modify tape cells beyond the${\displaystyle s(n)}$ cell from the left is sufficient.

A language that is decided by some ATM in time${\displaystyle c\cdot t(n)}$ for some constant${\displaystyle c>0}$ is said to be in the class${\displaystyle \mathsf{A}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(t(n))}$, and a language decided in space${\displaystyle c\cdot s(n)}$ is said to be in the class${\displaystyle \mathsf{A}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(s(n))}$.

Perhaps the most natural problem for alternating machines to solve is thequantified Boolean formula problem, which is a generalization of theBoolean 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}$.

TheBoolean 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.

The followingcomplexity 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 ofP,PSPACE, andEXPTIME, considering the resources used by an ATM rather than a deterministic Turing machine. Chandra, Kozen, and Stockmeyer^[3] proved that, for all${\displaystyle f(n)\ge \log (n)}$ and${\displaystyle g(n)\ge \log (n)}$:

• ${\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),}$

In particular:

• ALOGSPACE = P
• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME =EXPSPACE

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

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(October 2013) (Learn how and when to remove this message)

Analternating Turing machine withk alternations is an alternating Turing machine that switches from an existential to a universal state or vice versa no more thank−1 times. (It is an alternating Turing machine whose states are divided intok 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 seti and a state in setj <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 thejth 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.

Consider thecircuit minimization problem: given a circuitA computing aBoolean functionf and a numbern, determine if there is a circuit with at mostn gates that computes the same functionf. An alternating Turing machine, with one alternation, starting in an existential state, can solve this problem in polynomial time (by guessing a circuitB with at mostn gates, then switching to a universal state, guessing an input, and checking that the output ofB on that input matches the output ofA on that input).

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

As a corollary of theImmerman–Szelepcsényi theorem, the logarithmic space hierarchy collapses to its first level.^[4] 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 )}$ isspace constructible^{[citation needed]}.

An alternating Turing machine in polynomial time withk 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}$).^[5]These classes are sometimes denoted${\displaystyle {\mathrm{\Sigma }}_k\mathrm{P}}$ and${\displaystyle {\mathrm{\Pi }}_k\mathrm{P}}$, respectively.See thepolynomial hierarchy article for details.

Another special case of time hierarchies is thelogarithmic hierarchy.

• Michael Sipser (2006).Introduction to the Theory of Computation (2nd ed.). PWS Publishing.ISBN 978-0-534-95097-2. Section 10.3: Alternation, pp. 380–386.
• Christos Papadimitriou (1993).Computational Complexity (1st ed.). Addison Wesley.ISBN 978-0-201-53082-7. Section 16.2: Alternation, pp. 399–401.
• Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990), Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (eds.),"Alternation",Structural Complexity II, Berlin, Heidelberg: Springer, pp. 63–96,doi:10.1007/978-3-642-75357-2_4,ISBN 978-3-642-75357-2, retrieved2025-05-19
• Bakhadyr Khoussainov;Anil Nerode (2012).Automata Theory and its Applications. Springer Science & Business Media.ISBN 978-1-4612-0171-7.

• Models of computation

• Articles with short description
• Short description matches Wikidata
• Articles lacking in-text citations from May 2011
• All articles lacking in-text citations
• Articles needing additional references from October 2013
• All articles needing additional references
• All articles with unsourced statements
• Articles with unsourced statements from August 2010