交替式圖靈機

交替式圖靈機（英語：Alternating Turing Machine, ATM）是計算複雜度理論中定義的一種非確定型圖靈機（NTM）。與一般非確定型圖靈機不同，交替式圖靈機將接受語言的規則一般化到NP和反NP。交替式圖靈機的概念由Chandra和Stockmeyer（英語：Larry Stockmeyer）於1976年提出。

定義

直觀描述

NP的定義中使用了語言的存在形式，亦即如果存在一個選擇都能夠使得圖靈機達到接受狀態，那麼整個語言就能夠被接受。與此對應，反NP的定義中使用了語言的全稱形式，亦即整個語言被接受，若且唯若每一個選擇都達到一個接受狀態。結合這兩個定義，可以給出一個語言被交替式圖靈機接受的定義。

對一台交替式圖靈機而言，狀態集被劃分為兩部分：存在狀態（existential state）和全稱狀態（universal state）。存在狀態的接受條件為如果該狀態存在一種轉移序列到達接受狀態，而全稱狀態的接受條件為對該狀態而言，任何一種轉移序列都能夠到達接受狀態。（因而，一個不包含任何轉移的全稱狀態無條件接受，而一個不包含任何轉移的存在狀態無條件拒絕。）互動式圖靈機接受此語言，若且唯若初始狀態得到接受。

形式化描述

形式地，一台（單帶）交替式圖靈機是一個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\})}$被稱為轉移函數（${\displaystyle L}$代表帶頭左移，${\displaystyle R}$代表帶頭右移）
• ${\displaystyle q_{0}\in Q}$是初始狀態
• ${\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}$定義每個狀態的類型，其中${\displaystyle \wedge }$代表全稱狀態，${\displaystyle \vee }$代表存在狀態。

如果${\displaystyle M}$的格局在狀態${\displaystyle q\in Q}$中，且${\displaystyle g(q)=accept}$，那麼，格局為接受格局。如果格局滿足${\displaystyle g(q)=reject}$，那麼，格局為拒絕格局。對于格局滿足${\displaystyle g(q)=\wedge }$，該格局接受若且唯若所有一步之內能夠到達的格局是接受格局。反之，如果這些格局中存在一個格局拒絕，那麼拒絕。對于格局滿足${\displaystyle g(q)=\vee }$，該格局接受若且唯若存在一個一步之內能夠到達的格局是接受格局。反之，如果所有一步之內可達的格局拒絕，那麼拒絕。${\displaystyle M}$接受輸入串${\displaystyle w}$，如果${\displaystyle M}$的初始格局（即${\displaystyle M}$的狀態為${\displaystyle q_{0}}$，帶頭在帶的最左端，帶中包含${\displaystyle w}$）被接受。否則，${\displaystyle M}$拒絕${\displaystyle w}$。

k次交替圖靈機

k次交替圖靈機是一種將存在狀態和全稱狀態互相轉移次數限定在 ${\displaystyle k-1}$ 次的交替式圖靈機。亦即，定義狀態集${\displaystyle Q=\bigcup _{n=1}^{k}{Q_{k}}}$，其中，狀態集${\displaystyle Q_{2k+1}}$為存在狀態，狀態集 ${\displaystyle Q_{2k}}$ 為全稱狀態（或者相反）。並且，不存在從 ${\displaystyle Q_{i}}$ 到 ${\displaystyle Q_{j}}$ 的狀態轉移滿足 ${\displaystyle i>j}$。

例如，考慮以下電路最小化問題：給定一個能夠計算布林函數 ${\displaystyle f}$ 的電路 ${\displaystyle A}$ 和一個整數 ${\displaystyle n}$，確定是否存在一個最多包含${\displaystyle n}$個門的電路${\displaystyle B}$可以計算${\displaystyle f}$。一台2次交替圖靈機從一個存在狀態出發可以在多項式時間內解決這個問題（在存在狀態通過猜測電路 ${\displaystyle B}$ 的 ${\displaystyle n}$ 個門，此後進入全稱狀態，猜測輸入並檢查輸出是否和 ${\displaystyle A}$ 相同）。

一台從存在狀態（或者全稱狀態）出發的${\displaystyle k}$次交替圖靈機可以在多項式時間內解決${\displaystyle \Sigma _{k}{\rm {P}}}$（或者${\displaystyle \Pi _{k}{\rm {P}}}$）的問題。參見多項式時間分層。

資源上界

在利用上面的定義確定一台交替式圖靈機是否接受或拒絕某一格局時，並不需要檢查當前格局可以到達的所有格局。具體來說，對於存在格局，如果某一將來格局被接受即可標記為接受。對全稱格局，如果某一將來格局被拒絕，則可被標記為拒絕。

對於執行時間，規定一台ATM在${\displaystyle t(n)}$時間內判定一個形式語言，如果對於任意長度為${\displaystyle n}$的輸入，通過${\displaystyle t(n)}$步檢查（必要的）格局即可接受或拒絕初始格局。對於執行空間，規定一台ATM在${\displaystyle s(n)}$空間內判定一個形式語言，如果至多修改圖靈機帶上從左端起${\displaystyle s(n)}$位即可完成對必要格局的檢查。

如果一個語言在${\displaystyle c\cdot t(n)}$時間內（${\displaystyle c}$為正常數）被某個ATM判定，那麼，該語言屬於${\displaystyle {\rm {ATIME}}(t(n))}$。類似地，一個語言在${\displaystyle c\cdot s(n)}$空間內被某個ATM判定，那麼，該語言屬於${\displaystyle {\rm {ASPACE}}(s(n))}$。

例子

也許交替式圖靈機解決的最簡單的問題是量詞布林公式問題。這一問題是布林可滿足性問題的擴充，即每個變數可以被一個全稱量詞或存在量詞所約束。交替式圖靈機依照約束的次序對每一個存在量詞尋找一個可能的賦值，對每一個全稱量詞尋找所有的賦值。在對所有約束變數確定值之後，交替式圖靈機根據剩餘的布林公式確定接受還是拒絕。因此，接受一個存在量詞意味着存在一個賦值，使得賦值後的量詞布林公式可滿足。類似地，接受一個全稱量詞意味着對任何一個賦值，賦值後的量詞布林公式可滿足。

在ATM中，解決量詞布林公式問題需要${\displaystyle n^{2}}$時間和${\displaystyle n}$空間。

布林可滿足性問題可被視為量詞布林公式問題將所有變數約束為存在量詞的特例。從而普通的非確定型圖靈機可以有效地解決這一問題。

相關複雜度類別

下面的複雜度類別由ATM確定：

• ${\displaystyle {\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})}$是ATM在多項式時間內判定的語言集合
• ${\displaystyle {\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})}$是ATM在多項式空間內判定的語言集合
• ${\displaystyle {\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. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Section 10.3: Alternation, pp.348–354.
• （英文）Michael Sipser. Introduction to the Theory of Computation, 2nd ed.. PWS Publishing. 2006. ISBN 0-534-95097-3. Section 10.3: Alternation, pp.380–386.
• （英文）Christos Papadimitriou. Computational Complexity 1st edition. Addison Wesley. 1993. ISBN 0-201-53082-1. 引文格式1維護：冗餘文字 (link) Section 16.2: Alternation, pp.399–401.