交替式图灵机

交替式图灵机（英語：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.