Editing Alternating Turing machine (section)

== 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 <math>n^2</math> and space <math>n</math>.

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.