交替性チューリング機械
以下の複雑性クラスは ATM の定義に利用される。
A P = ⋃ k > 0 A T I M E ( n k ) {\displaystyle {\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})} は多項式時間で決定可能な言語である。
A P S P A C E = ⋃ k > 0 A S P A C E ( n k ) {\displaystyle {\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})} は多項式領域で決定可能な言語である。
A E X P T I M E = ⋃ k > 0 A T I M E ( k n ) {\displaystyle {\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})} は指数関数時間で決定可能な言語である。
これらは決定性チューリング機械よりも ATMでの計算資源を考慮したときの P、PSPACE、EXPTIME の定義に似ている。Chandra、Kozen、Stockmeyer は以下の定理を証明した。
AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE
これを並列計算原理と呼ぶ。
交替性チューリング機械(こうたいせいチューリングきかい、英: Alternating Turing Machine, ATM)は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。