Editing Alternating Turing machine (section)

== Bounded alternation ==

===Definition===
{{Unreferenced section|date=October 2013}}
An '''alternating Turing machine with ''k'' alternations''' is an alternating Turing machine that 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'' &lt; ''i''.)

<math>\mathsf{ATIME}(C,j)=\Sigma_j \mathsf{TIME}(C)</math> is the class of languages decidable in time <math>f\in C</math> by a machine beginning in an existential state and alternating at most <math>j-1</math> times. It is called the {{mvar|j}}th level of the <math>\mathsf{TIME}(C)</math> hierarchy.

<math>\mathsf{coATIME}(C,j)=\Pi_j \mathsf{TIME}(C)</math> is defined in the same way, but beginning in a universal state; it consists of the complements of the languages in <math>\mathsf{ATIME}(f,j)</math>.

<math>\mathsf{ASPACE}(C,j)=\Sigma_j \mathsf{SPACE}(C)</math> 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 ''collapses'' to level {{mvar|j}} if every language in level <math>k\ge j</math> of the hierarchy is in its level {{mvar|j}}.

As a corollary of the [[Immerman–Szelepcsényi theorem]], the logarithmic space hierarchy collapses to its first level.<ref>{{Cite journal|first1=Neil|last1=Immerman|url=http://www.cs.umass.edu/~immerman/pub/space.pdf|title=Nondeterministic space is closed under complementation|journal=[[SIAM Journal on Computing]]|volume=17|issue=5|year=1988|pages=935–938|doi=10.1137/0217058|citeseerx=10.1.1.54.5941}}</ref> As a corollary the <math>\mathsf{SPACE}(f)</math> hierarchy collapses to its first level when <math>f=\Omega(\log)</math> is [[space constructible]]{{Citation needed|date=August 2010}}.

===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 <math>\Sigma_k^p</math> (respectively, <math>\Pi_k^p</math>).<ref>{{cite book|last=Kozen|first=Dexter|author-link=Dexter Kozen|title=Theory of Computation|url=https://archive.org/details/theorycomputatio00koze|url-access=limited|publisher=[[Springer-Verlag]]|year=2006|page=[https://archive.org/details/theorycomputatio00koze/page/n67 58]|isbn=9781846282973}}</ref>
These classes are sometimes denoted <math>\Sigma_k\rm{P}</math> and <math>\Pi_k\rm{P}</math>, respectively.
See the [[polynomial hierarchy]] article for details.

Another special case of time hierarchies is the [[LH (complexity)|logarithmic hierarchy]].