Alternating Turing machine
Encyclopedia
In computational complexity theory
, an alternating Turing machine (ATM) is a non-deterministic Turing machine
(NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity class
es NP
and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer
in 1976 (see References).
An alternating Turing machine is a non-deterministic Turing machine
whose states are divided into two sets: existential states and universal state
s. 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.
where
If M is in a state
with 
then that configuration is said to be accepting, and if 
the configuration is said to be rejecting. A configuration with 
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 
is said to be accepting when there exists some configuration reachable in one step which is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in an NTM). M is said to accept an input string w if the initial configuration of M (the state of M is 
, the head is at the left end of the tape, and the tape contains w) is accepting, and to reject if the initial configuration is rejecting.
An ATM decides a formal language
in time
if, on any input of length 
, examining configurations only up to 
steps is sufficient to label the initial configuration as accepting or rejecting. An ATM decides a language in space 
if examining configurations which do not modify tape cells beyond the 
cell from the left is sufficient.
A language which is decided by some ATM in time
for some constant 
is said to be in the class 
, and a language decided in space 
is said to be in the class 
.
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 or rejects according as the resulting boolean formula evaluates to true or false. Thus at an existentially quantified variable the machine is accepting if a value can be substituted for the variable which 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
and space 
.
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.
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
When
and 
This is expressed by the Parallel computation thesis
.
is the class of function in time 
beginning by existential state and alternating at most 
times. It is called the 
th level of the 
hierarchy.
is the same classes, but beginning by a universal state, it is the complement of the language of 
.
is defined similarly for space bounded computation.
if every language in level 
of a hierarchy is in its level 
.
As a corollary of Immerman–Szelepcsényi theorem, the logarithm space hierarchy collapse to its first level. As a corollary the
hierarchy collapse to the first level when 
is space constructible.
(respectively, 
). See the polynomial hierarchy
article.
Another special case of time hierarchies is the logarithmic hierarchy
.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, an alternating Turing machine (ATM) is a non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
(NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
es NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer
Larry Stockmeyer
Larry Joseph Stockmeyer was a computer scientist. He was one of the pioneers in the field of computational complexity theory, and he also worked in the field of distributed computing...
in 1976 (see References).
Informal description
The definition of NP uses the existential mode of computation: if any choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses the universal mode of computation: only if all choices lead to an accepting state, then the whole computation accepts. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes.An alternating Turing machine is a non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
whose states are divided into two sets: existential states and universal state
Universal state
Universal state may refer to*Universal state , as used in reference to A Study of History, a work by historian Toynbee.*Universal state , a concept in the study of computational complexity...
s. 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.
Formal definition
Formally, a (one-tape) alternating Turing machine is a 5-tupleTuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
where-
is the finite set of states -
is the finite tape alphabet -
is called the transition function (L shifts the head left and R shifts the head right) -
is the initial state -
specifies the type of each state
If M is in a state
with then that configuration is said to be accepting, and if the configuration is said to be rejecting. A configuration with 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 is said to be accepting when there exists some configuration reachable in one step which is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in an NTM). M is said to accept an input string w if the initial configuration of M (the state of M is , the head is at the left end of the tape, and the tape contains w) is accepting, and to reject if the initial configuration is rejecting.Resource bounds
When deciding if a configuration of an ATM is accepting or rejecting using the above definition, it is not 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 a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
in time
if, on any input of length , examining configurations only up to steps is sufficient to label the initial configuration as accepting or rejecting. An ATM decides a language in space if examining configurations which do not modify tape cells beyond the cell from the left is sufficient.A language which is decided by some ATM in time
for some constant is said to be in the class , and a language decided in space is said to be in the class .Example
Perhaps the simplest problem for alternating machines to solve is the quantified boolean formula problem, which is a generalization of the boolean satisfiability problemBoolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
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 or rejects according as the resulting boolean formula evaluates to true or false. Thus at an existentially quantified variable the machine is accepting if a value can be substituted for the variable which 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
and space .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:-
are the languages decidable in polynomial time -
are the languages decidable in polynomial space -
are the languages decidable in exponential time
These are similar to the definitions of P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
, PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, and EXPTIME
EXPTIME
In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
, considering the resources used by an ATM rather than a deterministic Turing machine. Chandra, Kozen, and Stockmeyer proved the theorems
- AP = PSPACE
- APSPACE = EXPTIME
- AEXPTIME = EXPSPACEEXPSPACEIn complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n...
-
-
-
When
and This is expressed by the Parallel computation thesis
Parallel computation thesis
In computational complexity theory, the parallel computation thesis is a hypothesis which states that the time used by a parallel machine is polynomially related to the space used by a sequential machine...
.
Definition
An alternating Turing machine with k alternations is an alternating Turing machine which 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.) is the class of function in time beginning by existential state and alternating at most times. It is called the th level of the hierarchy. is the same classes, but beginning by a universal state, it is the complement of the language of . 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 collapse to level if every language in level of a hierarchy is in its level .As a corollary of Immerman–Szelepcsényi theorem, the logarithm space hierarchy collapse to its first level. As a corollary the
hierarchy collapse to the first level when 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 (respectively, ). See the polynomial hierarchyPolynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
article.
Another special case of time hierarchies is the logarithmic hierarchy
LH (complexity)
Logarithmic Hierarchy is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternation. It is a special case of hierarchy of bounded alternating Turing machine...
.