交代チューリングマシン

計算複雑性理論において、交代チューリングマシン( ATM ) は、計算を受け入れるためのルールを持つ非決定性チューリングマシン( NTM ) であり、計算複雑性クラス NPとco-NPの定義で使用されるルールを一般化します。 ATM の概念は、1976 年にChandraとStockmeyer ^[1]によって提唱され、 Kozen ^[2]によって独立に提唱され、1981 年に共同ジャーナルに掲載されました。^[3]

NP の定義では、存在的計算モードを使用します。つまり、いずれかの選択が受け入れ状態につながる場合、計算全体が受け入れます。co-NP の定義では、普遍的計算モードを使用します。つまり、すべての選択が受け入れ状態につながる場合にのみ、計算全体が受け入れます。交代チューリング マシン (または、より正確には、そのようなマシンの受け入れの定義) は、これらのモードを交互に実行します。

交代チューリングマシンは、状態が存在状態と普遍状態の 2 つのセットに分かれている非決定性チューリングマシンです。存在状態は、何らかの遷移が受け入れ状態につながる場合に受け入れます。普遍状態は、すべての遷移が受け入れ状態につながる場合に受け入れます。(したがって、遷移のない普遍状態は無条件に受け入れ、遷移のない存在状態は無条件に拒否します)。マシン全体としては、初期状態が受け入れである場合に受け入れます。

正式には、（1テープ）交代チューリングマシンは5組の組 であり、 ${\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}$

• ${\displaystyle Q}$状態の有限集合である
• ${\displaystyle \Gamma }$有限テープアルファベット
• ${\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}$遷移関数と呼ばれる（Lは頭を左にシフトし、Rは頭を右にシフトする）
• ${\displaystyle q_{0}\in Q}$初期状態
• ${\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}$各状態のタイプを指定します

M がの状態にある場合、その構成はを受け入れているとされ、 の場合は を拒否しているとされます。 を持つ構成は、1 ステップで到達可能なすべての構成が受け入れている場合は を受け入れているとされ、1 ステップで到達可能な一部の構成が拒否している場合は を拒否しているとされます。 を持つ構成は、1 ステップで到達可能な一部の構成が存在し、それが受け入れている場合は を受け入れているとされ、1 ステップで到達可能なすべての構成が拒否している場合は を拒否しているとされます (これは、最終状態を除く従来の NTM のすべての状態のタイプです)。 Mの初期構成( Mの状態は で、ヘッドはテープの左端にあり、テープにはwが含まれています)が受け入れている場合はMが入力文字列 wを受け入れると言われ、初期構成が拒否している場合は を拒否するとされます。 ${\displaystyle q\in Q}$${\displaystyle g(q)=accept}$${\displaystyle g(q)=reject}$${\displaystyle g(q)=\wedge }$${\displaystyle g(q)=\vee }$${\displaystyle q_{0}}$

構成が受け入れと拒否の両方を行うことは不可能ですが、計算が終了しない可能性があるため、一部の構成は受け入れも拒否も行わない場合があります。

上記の定義を使用して ATM の構成が受け入れ可能か拒否可能かを判断する場合、現在の構成から到達可能なすべての構成を必ずしも調べる必要はありません。特に、後続の構成が受け入れ可能であることが判明した場合は、存在構成を受け入れ可能とラベル付けすることができ、後続の構成が拒否可能であることが判明した場合は、普遍構成を拒否可能とラベル付けすることができます。

ATM は、長さnの任意の入力に対して、ステップまでの構成のみを調べることで、初期構成を受け入れまたは拒否としてラベル付けするのに十分である場合、時間内で形式言語を決定します。ATM は、左からセルを超えてテープ セルを変更しない構成を調べることで十分である場合、空間内で言語を決定します。 ${\displaystyle t(n)}$${\displaystyle t(n)}$${\displaystyle s(n)}$${\displaystyle s(n)}$

ある定数に対してある ATM によって時間的に決定される言語はクラス に属すると言われ、空間的に決定される言語はクラス に属すると言われます。 ${\displaystyle c\cdot t(n)}$${\displaystyle c>0}$${\displaystyle {\mathsf {ATIME}}(t(n))}$${\displaystyle c\cdot s(n)}$${\displaystyle {\mathsf {ASPACE}}(s(n))}$

おそらく、交代マシンが解くのに最も自然な問題は、量化ブール式問題です。これは、各変数が存在量指定子または全称量指定子のいずれかでバインドされるブール充足可能性問題の一般化です。交代マシンは、存在的に分岐して存在量指定変数のすべての可能な値を試し、普遍的に分岐して全称量指定変数のすべての可能な値を、バインドされている左から右の順序で試します。すべての量指定変数の値を決定した後、マシンは結果のブール式が true と評価された場合は受け入れ、false と評価された場合は拒否します。したがって、存在量指定変数では、マシンは、残りの問題が充足可能になる値を変数に置き換えることができるかどうかを受け入れ、全称量指定変数では、マシンは、任意の値を置き換えることができ、残りの問題が充足可能かどうかを受け入れます。

このようなマシンは、時間と空間内で定量化されたブール式を決定します。 ${\displaystyle n^{2}}$${\displaystyle n}$

ブール充足可能性問題は、すべての変数が存在的に量化され、存在分岐のみを使用する通常の非決定性によって効率的に解決できる特殊なケースとして考えることができます。

ATM に対して定義すると、次の複雑性クラスが役立ちます。

• ${\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}$言語は多項式時間で決定可能か
• ${\displaystyle {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}$言語は多項式空間で決定可能か
• ${\displaystyle {\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})}$言語は指数時間で決定可能か

これらは、決定論的チューリングマシンではなくATMが使用するリソースを考慮すると、P、PSPACE、EXPTIMEの定義に似ています。Chandra、Kozen、Stockmeyer ^[3]は定理を証明しました 。

• アログスペース = P
• AP = スペース
• AP スペース = EXP 時間
• AEXPTIME = EXPSPACE
• ${\displaystyle {\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})}$
• ${\displaystyle {\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))}$
• ${\displaystyle {\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),}$

いつ、そして。 ${\displaystyle f(n)\geq \log(n)}$${\displaystyle g(n)\geq \log(n)}$

これらの関係のより一般的な形式は、並列計算の命題によって表現されます。

k個の交代機能を持つ交代チューリング マシンは、存在状態から普遍状態へ、またはその逆への切り替えをk −1 回以内で行う交代チューリング マシンです。(状態がkセットに分割されている交代チューリング マシンです。偶数セットの状態は普遍状態であり、奇数セットの状態は存在状態です (またはその逆)。マシンには、セットiの状態とセットj < iの状態の間の遷移はありません。)

${\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}$存在状態から始まり、ほとんどの時間で交代するマシンによって時間的に決定可能な言語のクラスです。これは階層のj番目のレベルと呼ばれます。 ${\displaystyle f\in C}$${\displaystyle j-1}$${\displaystyle {\mathsf {TIME}}(C)}$

${\displaystyle {\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)}$は同じように定義されますが、普遍的な状態から始まります。これは、 の言語の補語から構成されます。 ${\displaystyle {\mathsf {ATIME}}(f,j)}$

${\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)}$空間制限のある計算の場合も同様に定義されます。

回路の最小化問題を考えてみましょう。ブール関数fと数値n を計算する回路Aが与えられた場合、同じ関数fを計算するゲートが最大でn個ある回路があるかどうかを判定します。交代が 1 回だけあり、存在状態から始まる交代チューリングマシンは、この問題を多項式時間で解決できます (最大でn個のゲートがある回路B を推測し、次にユニバーサル状態に切り替えて入力を推測し、その入力に対するBの出力がその入力に対するAの出力と一致することを確認することによって)。

階層のレベル内のすべての言語がレベルjにある場合、階層はレベルjに縮小されると言われます。 ${\displaystyle k\geq j}$

インメルマン・シェレプセニの定理の帰結として、対数空間階層はその最初のレベルに縮小する。^[4]帰結として、空間が構成可能であるとき、階層はその最初のレベルに縮小する^[要出典]。 ${\displaystyle {\mathsf {SPACE}}(f)}$${\displaystyle f=\Omega (\log )}$

k回の交代を伴う多項式時間の交代チューリングマシンは、存在状態（それぞれ、普遍状態）から始まり、クラス（それぞれ、）内のすべての問題を決定できます。^[5]これらのクラスは、それぞれおよびと 表記されることがあります。詳細については、 多項式階層の記事を参照してください。${\displaystyle \Sigma _{k}^{p}}$${\displaystyle \Pi _{k}^{p}}$${\displaystyle \Sigma _{k}{\rm {P}}}$${\displaystyle \Pi _{k}{\rm {P}}}$

時間階層のもう一つの特殊なケースは対数階層です。

• マイケル・シプサー（2006年）。計算理論入門（第2版）。PWS Publishing。ISBN 978-0-534-95097-2。セクション10.3: 交替、380～386ページ。
• Christos Papadimitriou (1993)。計算複雑性（第 1 版）。Addison Wesley。ISBN 978-0-201-53082-7。セクション16.2: 交替、399～401ページ。
• Bakhadyr Khoussainov、Anil Nerode (2012)。オートマトン理論とその応用。Springer Science & Business Media。ISBN 978-1-4612-0171-7。