交替性チューリング機械

交替性チューリング機械（こうたいせいチューリングきかい、英: Alternating Turing Machine, ATM）は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。

定義

概要

NP の定義では、計算の「存在的様式 (existential mode)」が使われる。すなわち、任意の選択が受理状態に到達すれば、計算全体が受理されたことになる。co-NP の定義では、計算の「全称的様式 (universal mode)」が使われる。すなわち、全ての選択が受理状態に到達すれば、計算状態が受理されたことになる。交替性チューリング機械（より正確に言えばそのような機械における受理の定義）はこれら2つの様式を混在して利用する。

交替性チューリング機械は非決定性チューリング機械の一種であり、その状態は2つの集合、「存在的状態 (existential states)」と「全称的状態 (universal states)」に分けられる。存在的状態では、受理状態となる遷移が1つでもあれば受理される。全称的状態では、全ての遷移が受理状態となる場合にのみ受理される。従って、遷移のない全称状態は無条件で受理され、遷移のない存在状態は無条件で拒絶される。機械全体としては、初期状態が受理される場合に受理する。

形式的定義

形式的には（テープが一本の）交替性チューリング機械は、5-タプル $M=(Q,\Gamma ,\delta ,q_{0},g)$ で表され、それぞれは以下のような意味を持つ。

$Q$ は、状態の有限集合
$\Gamma$ は、テープ上のアルファベットの有限集合
$\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$ は、遷移関数（L はヘッドを左に移動させ、R はヘッドを右に移動させる）
$q_{0}\in Q$ は、初期状態
$g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}$ は、各状態の種類を指定する関数

M が状態 $q\in Q$ にあり、 $g(q)=accept$ なら、受理状態であることを示している。また $g(q)=reject$ なら、拒絶状態であることを示している。 $g(q)=\wedge$ なら、1ステップで到達可能な全ての構成が受理状態であれば、受理状態であるし、1ステップで到達可能な状態の中に拒絶状態のものがあれば、拒絶状態である。 $g(q)=\vee$ なら、1ステップで到達可能な状態の中に受理状態のものがあれば、受理状態であるし、1ステップで到達可能な全ての構成が拒絶状態であれば、拒絶状態である（通常の NTM は全てこの状態）。M が入力文字列 w を受理するとは、M の初期構成（Mの状態が $q_{0}$ で、ヘッドはテープの左端にあり、テープには w がある）が受理状態であることを意味し、初期構成が拒絶状態なら拒絶する。

k回の交替のある機械

k回の交替のある交替性チューリング機械とは、存在的状態から全称的状態への切り替え、あるいはその逆の切り替えが k 回以上発生しない交替性チューリング機械である。この場合、状態は k 個の集合に分割される。状態が偶数個の集合に分割されるなら、全体として全称的であり、奇数個なら存在的となる（あるいは逆。初期状態がどちらであるかに依存する）。集合 i に含まれる状態と、j < i であるような集合 j に含まれる状態との間に遷移は存在しない。

例として回路最小化問題を考える。あるブール関数 f を計算する回路 A と数 n があるとき、最大 n 個の論理ゲートで同じ関数 f を計算する回路が存在するかどうかを決定する問題である。1回の交替のある交替性チューリング機械で存在的状態から動作を開始する場合、この問題を多項式時間で解くことができる。最大 n ゲートの回路 B を想定し、全称状態に交替し、入力を想定し、B にその入力を与えたときの出力と A に同じ入力を与えたときの出力を比較する。

k回の交替のある交替性チューリング機械が存在的状態から動作開始する場合、クラス $\Sigma _{k}{\rm {P}}$ に属する問題を多項式時間で解くことができる（あるいは、全称的状態から動作開始する場合は、 $\Pi _{k}{\rm {P}}$ ）。詳しくは多項式階層を参照されたい。

計算資源

上述の定義を使って、ある ATM の構成が受理状態なのか拒絶状態なのかを決定する場合、現在の構成から到達可能なあらゆる構成を全て調べる必要はない。特に存在的構成は、そこから遷移する構成に受理状態のものが1つでもあれば、受理状態であると言えるし、全称構成は、そこから遷移する構成に拒絶状態のものが1つでもあれば、拒絶状態であると言える。

ATM は、長さ $n$ の任意の入力が特定の形式言語に属するかを時間 $t(n)$ で決定する。すなわち、初期構成が受理状態か拒絶状態かを決定するのに、高々 $t(n)$ ステップまで構成を調べればよい。また、必要な領域は $s(n)$ で十分である。

ATM で、時間 $c\cdot t(n)$ （ $c>0$ は定数）で決定される言語は、クラス ${\rm {ATIME}}(t(n))$ に属し、領域 $c\cdot s(n)$ で決定される言語は、クラス ${\rm {ASPACE}}(s(n))$ に属する。

例

交替性チューリング機械で解ける最も単純な問題として限量記号付きブール式問題がある。これは充足可能性問題を拡張して、各変数が存在量化子か全称量化子で制限されるようにした問題である。交替性チューリング機械は、存在量化された変数については存在的に分岐して考えられる全ての値を試し、全称量化された変数については全称的に分岐して考えられる全ての値を試す。これを量化される順に左から右に見ていくのである。全ての量化変数の値を決定した後、論理式にそれらの値を適用して、その真理値によって受理か拒絶かを決定する。

このような機械は限量記号付きブール式を、時間 $n^{2}$ と領域 $n$ で決定する。

充足可能性問題は、全ての変数が存在量化された特殊ケースと見ることもでき、存在的様式だけで効率的に解ける。

複雑性クラスと決定性チューリング機械との比較

以下の複雑性クラスは ATM の定義に利用される。

${\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})$ は多項式時間で決定可能な言語である。
${\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})$ は多項式領域で決定可能な言語である。
${\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})$ は指数関数時間で決定可能な言語である。

これらは決定性チューリング機械よりも ATMでの計算資源を考慮したときの P、PSPACE、EXPTIME の定義に似ている。Chandra、Kozen、Stockmeyer は以下の定理を証明した。

AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE

これを並列計算原理と呼ぶ。

参考文献

Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Section 10.3: Alternation, pp.348–354.
Michael Sipser (2006年). Introduction to the Theory of Computation, 2nd ed.. PWS Publishing. ISBN 0-534-95097-3 Section 10.3: Alternation, pp.380–386.
Christos Papadimitriou (1993年). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1 Section 16.2: Alternation, pp.399–401.