Alternating Turing machine

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 classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer[1] and independently by Kozen[2] in 1976, with a joint journal publication in 1981.[3]

Definitions

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

An alternating Turing machine is a non-deterministic Turing machine whose states are divided into two sets: existential states and universal 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.

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.

Example

Perhaps the simplest 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 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.

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.

Bounded alternation

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

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  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.[4]

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.

Another special case of time hierarchies is the logarithmic hierarchy.

References

  1. ^Chandra, Ashok K.; Stockmeyer, Larry J. (1976). “Alternation”. Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 98–108. doi:10.1109/SFCS.1976.4.
  2. ^Kozen, D. (1976). “On parallelism in Turing machines”. Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 89–97. doi:10.1109/SFCS.1976.20. hdl:1813/7056.
  3. ^ Jump up to:ab Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). “Alternation” (PDF). Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. Archived from the original (PDF) on April 12, 2016.
  4. ^Immerman, Neil (1988). “Nondeterministic space is closed under complementation” (PDF). SIAM Journal on Computing. 17 (5): 935–938. CiteSeerX 10.1.1.54.5941. doi:10.1137/0217058.
  5. ^Kozen, Dexter (2006). Theory of Computation. Springer-Verlag. p. 58. ISBN 9781846282973.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library