Xrthnty

交替式图灵机（英语：Alternating Turing Machine, ATM）是计算复杂度理论中定义的一种非确定型图灵机（NTM）。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer（英语：Larry Stockmeyer）于1976年提出。

定义

直观描述

NP的定义中使用了语言的存在形式，亦即如果存在一个选择都能够使得图灵机达到接受状态，那么整个语言就能够被接受。与此对应，反NP的定义中使用了语言的全称形式，亦即整个语言被接受，当且仅当每一个选择都达到一个接受状态。结合这两个定义，可以给出一个语言被交替式图灵机接受的定义。

对一台交替式图灵机而言，状态集被划分为两部分：存在状态（existential state）和全称状态（universal state）。存在状态的接受条件为如果该状态存在一种转移序列到达接受状态，而全称状态的接受条件为对该状态而言，任何一种转移序列都能够到达接受状态。（因而，一个不包含任何转移的全称状态无条件接受，而一个不包含任何转移的存在状态无条件拒绝。）交互式图灵机接受此语言，当且仅当初始状态得到接受。

形式化描述

形式地，一台（单带）交替式图灵机是一个5元组M=(Q,Γ,δ,q0,g)displaystyle M=(Q,Gamma ,delta ,q_0,g)，其中

• 
  Qdisplaystyle Q是一个有限大小的状态集


• 
  Γdisplaystyle Gamma 是一个有限大小的字母表


• 
  δ:Q×Γ→P(Q×Γ×L,R)displaystyle delta :Qtimes Gamma rightarrow mathcal P(Qtimes Gamma times L,R)被称为转移函数（Ldisplaystyle L代表带头左移，Rdisplaystyle R代表带头右移）


• 
  q0∈Qdisplaystyle q_0in Q是初始状态


• 
  g:Q→∧,∨,accept,rejectdisplaystyle g:Qrightarrow wedge ,vee ,accept,reject定义每个状态的类型，其中∧displaystyle wedge 代表全称状态，∨displaystyle vee 代表存在状态。

如果Mdisplaystyle M的格局在状态q∈Qdisplaystyle qin Q中，且g(q)=acceptdisplaystyle g(q)=accept，那么，格局为接受格局。如果格局满足g(q)=rejectdisplaystyle g(q)=reject，那么，格局为拒绝格局。对于格局满足g(q)=∧displaystyle g(q)=wedge ，该格局接受当且仅当所有一步之内能够到达的格局是接受格局。反之，如果这些格局中存在一个格局拒绝，那么拒绝。对于格局满足g(q)=∨displaystyle g(q)=vee ，该格局接受当且仅当存在一个一步之内能够到达的格局是接受格局。反之，如果所有一步之内可达的格局拒绝，那么拒绝。Mdisplaystyle M接受输入串wdisplaystyle w，如果Mdisplaystyle M的初始格局（即Mdisplaystyle M的状态为q0displaystyle q_0，带头在带的最左端，带中包含wdisplaystyle w）被接受。否则，Mdisplaystyle M拒绝wdisplaystyle w。

k次交替图灵机

k次交替图灵机是一种将存在状态和全称状态互相转移次数限定在 k−1displaystyle k-1 次的交替式图灵机。亦即，定义状态集Q=⋃n=1kQkdisplaystyle Q=bigcup _n=1^kQ_k，其中，状态集Q2k+1displaystyle Q_2k+1为存在状态，状态集 Q2kdisplaystyle Q_2k 为全称状态（或者相反）。并且，不存在从 Qidisplaystyle Q_i 到 Qjdisplaystyle Q_j 的状态转移满足 i>jdisplaystyle i>j。

例如，考虑以下电路最小化问题：给定一个能够计算布尔函数 fdisplaystyle f 的电路 Adisplaystyle A 和一个整数 ndisplaystyle n，确定是否存在一个最多包含ndisplaystyle n个门的电路Bdisplaystyle B可以计算fdisplaystyle f。一台2次交替图灵机从一个存在状态出发可以在多项式时间内解决这个问题（在存在状态通过猜测电路 Bdisplaystyle B 的 ndisplaystyle n 个门，此后进入全称状态，猜测输入并检查输出是否和 Adisplaystyle A 相同）。

一台从存在状态（或者全称状态）出发的kdisplaystyle k次交替图灵机可以在多项式时间内解决ΣkPdisplaystyle Sigma _krm P（或者ΠkPdisplaystyle Pi _krm P）的问题。参见多项式时间分层。

资源上界

在利用上面的定义确定一台交替式图灵机是否接受或拒绝某一格局时，并不需要检查当前格局可以到达的所有格局。具体来说，对于存在格局，如果某一将来格局被接受即可标记为接受。对全称格局，如果某一将来格局被拒绝，则可被标记为拒绝。

对于运行时间，规定一台ATM在t(n)displaystyle t(n)时间内判定一个形式语言，如果对于任意长度为ndisplaystyle n的输入，通过t(n)displaystyle t(n)步检查（必要的）格局即可接受或拒绝初始格局。对于运行空间，规定一台ATM在s(n)displaystyle s(n)空间内判定一个形式语言，如果至多修改图灵机带上从左端起s(n)displaystyle s(n)位即可完成对必要格局的检查。

如果一个语言在c⋅t(n)displaystyle ccdot t(n)时间内（cdisplaystyle c为正常数）被某个ATM判定，那么，该语言属于ATIME(t(n))displaystyle rm ATIME(t(n))。类似地，一个语言在c⋅s(n)displaystyle ccdot s(n)空间内被某个ATM判定，那么，该语言属于ASPACE(s(n))displaystyle rm ASPACE(s(n))。

例子

也许交替式图灵机解决的最简单的问题是量词布尔公式问题。这一问题是布尔可满足性问题的扩充，即每个变量可以被一个全称量词或存在量词所约束。交替式图灵机依照约束的次序对每一个存在量词寻找一个可能的赋值，对每一个全称量词寻找所有的赋值。在对所有约束变量确定值之后，交替式图灵机根据剩余的布尔公式确定接受还是拒绝。因此，接受一个存在量词意味着存在一个赋值，使得赋值后的量词布尔公式可满足。类似地，接受一个全称量词意味着对任何一个赋值，赋值后的量词布尔公式可满足。

在ATM中，解决量词布尔公式问题需要n2displaystyle n^2时间和ndisplaystyle n空间。

布尔可满足性问题可被视为量词布尔公式问题将所有变量约束为存在量词的特例。从而普通的非确定型图灵机可以有效地解决这一问题。

相关复杂度类

下面的复杂度类由ATM确定：

• 
  AP=⋃k>0ATIME(nk)displaystyle rm AP=bigcup _k>0rm ATIME(n^k)是ATM在多项式时间内判定的语言集合


• 
  APSPACE=⋃k>0ASPACE(nk)displaystyle rm APSPACE=bigcup _k>0rm ASPACE(n^k)是ATM在多项式空间内判定的语言集合


• 
  AEXPTIME=⋃k>0ATIME(kn)displaystyle rm AEXPTIME=bigcup _k>0rm ATIME(k^n)是ATM在指数时间内判定的语言集合

这些定义与确定性图灵机给定的P、PSPACE和EXPTIME在空间上类似。对于两种计算模型导出的两类复杂度类，Chandra、Kozen和Stockmeyer证明了以下定理：

• AP = PSPACE


• APSPACE = EXPTIME


• AEXPTIME = EXPSPACE
  

这些结论在并行计算理论中阐释。

参见

• 图灵机


• 非确定型图灵机

参考资料

zhonggoufulcaipiao2013.8.6ri,kaijianghaoma02.08.15.16.20.30-01

• 
  （英文）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.

查 论 编 重要的複雜度類（完整列表） 易解复杂度类 对数空间相关 DLOGTIME AC0（英语：AC0） ACC0（英语：ACC0） TC0（英语：TC0） L · FL · SL · NL NC SC PolyL 多项式空间相关 P（P-完全） FP（英语：FP (complexity)） ZPP RP BPP BQP（QMA（英语：QMA） PostBQP（英语：PostBQP） EQP（英语：EQP）） 怀疑难解复杂度类 UP NP（NP完全 NP困难 反NP 反NP完全（英语：co-NP-complete）） FNP（英语：FNP (complexity)）（TFNP（英语：TFNP (complexity)）） PH PP #P（#P-完全（英语：Sharp-P-complete）） PSPACE（PSPACE完全（英语：PSPACE-complete）） 难解复杂度类 EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL 复杂度类的谱系 多项式谱系（英语：Polynomial hierarchy） 指數譜系 Grzegorczyk谱系（英语：Grzegorczyk hierarchy） 算术谱系 相关复杂度族 DTIME NTIME DSPACE（英语：DSPACE） NSPACE 可能性核对证明（英语：Probabilistically checkable proof） 交互式证明系统 量子复杂性理论