Editing Alternating Turing machine (section)

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