Can you summarize the following document?
        
  

  NP的定義中使用了語言的存在形式,亦即如果存在一個選擇都能夠使得圖靈機達到接受狀態,那麼整個語言就能夠被接受。與此對應,反NP的定義中使用了語言的全稱形式,亦即整個語言被接受,當且僅當每一個選擇都達到一個接受狀態。結合這兩個定義,可以給出一個語言被交替式圖靈機接受的定義。  對一臺交替式圖靈機而言,狀態集被劃分為兩部分:存在狀態(existential state)和全稱狀態(universal state)。存在狀態的接受條件為如果該狀態存在一種轉移序列到達接受狀態,而全稱狀態的接受條件為對該狀態而言,任何一種轉移序列都能夠到達接受狀態。(因而,一個不包含任何轉移的全稱狀態無條件接受,而一個不包含任何轉移的存在狀態無條件拒絕。)互動式圖靈機接受此語言,當且僅當初始狀態得到接受。

  形式地,一臺(單帶)交替式圖靈機是一個5元組formula_1,其中  如果formula_11的格局在狀態formula_12中,且formula_13,那麼,格局為接受格局。如果格局滿足formula_14,那麼,格局為拒絕格局。對於格局滿足formula_15,該格局接受當且僅當所有一步之內能夠到達的格局是接受格局。反之,如果這些格局中存在一個格局拒絕,那麼拒絕。對於格局滿足formula_16,該格局接受當且僅當存在一個一步之內能夠到達的格局是接受格局。反之,如果所有一步之內可達的格局拒絕,那麼拒絕。formula_11接受輸入串formula_18,如果formula_11的初始格局(即formula_11的狀態為formula_21,帶頭在帶的最左端,帶中包含formula_18)被接受。否則,formula_11拒絕formula_18。

  "k"次交替圖靈機是一種將存在狀態和全稱狀態互相轉移次數限定在 formula_25 次的交替式圖靈機。亦即,定義狀態集formula_26,其中,狀態集formula_27為存在狀態,狀態集 formula_28 為全稱狀態(或者相反)。並且,不存在從 formula_29 到 formula_30 的狀態轉移滿足 formula_31。  例如,考慮以下電路最小化問題:給定一個能夠計算布林函式 formula_32 的電路 formula_33 和一個整數 formula_34,確定是否存在一個最多包含formula_34個門的電路formula_36可以計算formula_32。一臺2次交替圖靈機從一個存在狀態出發可以在多項式時間內解決這個問題(在存在狀態通過猜測電路 formula_36 的 formula_34 個門,此後進入全稱狀態,猜測輸入並檢查輸出是否和 formula_33 相同)。  一臺從存在狀態(或者全稱狀態)出發的formula_41次交替圖靈機可以在多項式時間內解決formula_42(或者formula_43)的問題。參見多項式時間分層。

  在利用上面的定義確定一臺交替式圖靈機是否接受或拒絕某一格局時,並不需要檢查當前格局可以到達的所有格局。具體來說,對於存在格局,如果某一將來格局被接受即可標記為接受。對全稱格局,如果某一將來格局被拒絕,則可被標記為拒絕。  對於執行時間,規定一臺ATM在formula_44時間內判定一個形式語言,如果對於任意長度為formula_34的輸入,通過formula_44步檢查(必要的)格局即可接受或拒絕初始格局。對於執行空間,規定一臺ATM在formula_47空間內判定一個形式語言,如果至多修改圖靈機帶上從左端起formula_47位即可完成對必要格局的檢查。  如果一個語言在formula_49時間內(formula_50為正常數)被某個ATM判定,那麼,該語言屬於formula_51。類似地,一個語言在formula_52空間內被某個ATM判定,那麼,該語言屬於formula_53。

  也許交替式圖靈機解決的最簡單的問題是量詞布林公式問題。這一問題是布林可滿足性問題的擴充,即每個變數可以被一個全稱量詞或存在量詞所約束。交替式圖靈機依照約束的次序對每一個存在量詞尋找一個可能的賦值,對每一個全稱量詞尋找所有的賦值。在對所有約束變數確定值之後,交替式圖靈機根據剩餘的布林公式確定接受還是拒絕。因此,接受一個存在量詞意味著存在一個賦值,使得賦值後的量詞布林公式可滿足。類似地,接受一個全稱量詞意味著對任何一個賦值,賦值後的量詞布林公式可滿足。  在ATM中,解決量詞布林公式問題需要formula_54時間和formula_34空間。  布林可滿足性問題可被視為量詞布林公式問題將所有變數約束為存在量詞的特例。從而普通的非確定型圖靈機可以有效地解決這一問題。

  下面的複雜度類由ATM確定:  這些定義與確定性圖靈機給定的P、PSPACE和EXPTIME在空間上類似。對於兩種計算模型匯出的兩類複雜度類,Chandra、Kozen和Stockmeyer證明了以下定理:  這些結論在平行計算理論中闡釋。

  zhonggoufulcaipiao2013.8.6ri,kaijianghaoma02.08.15.16.20.30-01
交替式圖靈機(, ATM)是計算複雜度理論中定義的一種非確定型圖靈機(NTM)。與一般非確定型圖靈機不同,交替式圖靈機將接受語言的規則一般化到NP和反NP。交替式圖靈機的概念由Chandra和Stockmeyer於1976年提出。