交替性チューリング機械
形式的には(テープが一本の)交替性チューリング機械は、5-タプル M = ( Q , Γ , δ , q 0 , g ) {\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)} で表され、それぞれは以下のような意味を持つ。
Q {\displaystyle Q} は、状態の有限集合
Γ {\displaystyle \Gamma } は、テープ上のアルファベットの有限集合
δ : Q × Γ → P ( Q × Γ × { L , R } ) {\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})} は、遷移関数(L はヘッドを左に移動させ、R はヘッドを右に移動させる)
q 0 ∈ Q {\displaystyle q_{0}\in Q} は、初期状態
g : Q → { ∧ , ∨ , a c c e p t , r e j e c t } {\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}} は、各状態の種類を指定する関数
k回の交替のある交替性チューリング機械とは、存在的状態から全称的状態への切り替え、あるいはその逆の切り替えが k 回以上発生しない交替性チューリング機械である。この場合、状態は k 個の集合に分割される。状態が偶数個の集合に分割されるなら、全体として全称的であり、奇数個なら存在的となる(あるいは逆。初期状態がどちらであるかに依存する)。集合 i に含まれる状態と、j < i であるような集合 j に含まれる状態との間に遷移は存在しない。
例として回路最小化問題を考える。あるブール関数 f を計算する回路 A と数 n があるとき、最大 n 個の論理ゲートで同じ関数 f を計算する回路が存在するかどうかを決定する問題である。1回の交替のある交替性チューリング機械で存在的状態から動作を開始する場合、この問題を多項式時間で解くことができる。最大 n ゲートの回路 B を想定し、全称状態に交替し、入力を想定し、B にその入力を与えたときの出力と A に同じ入力を与えたときの出力を比較する。
k回の交替のある交替性チューリング機械が存在的状態から動作開始する場合、クラス Σ k P {\displaystyle \Sigma _{k}{\rm {P}}} に属する問題を多項式時間で解くことができる(あるいは、全称的状態から動作開始する場合は、 Π k P {\displaystyle \Pi _{k}{\rm {P}}} )。詳しくは多項式階層を参照されたい。