Editing Alternating Turing machine (section)

== Complexity classes and comparison to deterministic Turing machines ==

The following [[complexity classes]] are useful to define for ATMs:
* <math>\mathsf{AP}=\bigcup_{k>0}\mathsf{ATIME}(n^k)</math> are the languages decidable in polynomial time
* <math>\mathsf{APSPACE}=\bigcup_{k>0}\mathsf{ASPACE}(n^k)</math> are the languages decidable in polynomial space
* <math>\mathsf{AEXPTIME}=\bigcup_{k>0}\mathsf{ATIME}(2^{n^k})</math> are the languages decidable in exponential time

These are similar to the definitions of [[P (complexity)|P]], [[PSPACE]], and [[EXPTIME]], considering the resources used by an ATM rather than a deterministic Turing machine.  Chandra, Kozen, and Stockmeyer<ref name=alternation /> proved that, for all <math>f(n)\ge\log(n)</math> and <math>g(n)\ge\log(n)</math>:
* <math>\mathsf{ASPACE}(f(n))=\bigcup_{c>0}\mathsf{DTIME}(2^{cf(n)})=\mathsf{DTIME}(2^{O(f(n))})</math>
* <math>\mathsf{ATIME}(g(n))\subseteq \mathsf{DSPACE}(g(n))</math>
* <math>\mathsf{NSPACE}(g(n))\subseteq\bigcup_{c>0}\mathsf{ATIME}(c\times g(n)^2),</math>
In particular:
* ALOGSPACE = P
* AP = PSPACE
* APSPACE = EXPTIME
* AEXPTIME = [[EXPSPACE]]
A more general form of these relationships is expressed by the [[parallel computation thesis]].