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 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.
Read more about this topic: Alternating Turing Machine
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)