If $\mathbf{P}=\mathbf{NP}$, then $\mathbf N=1$ or $\mathbf{P}=0$.
—-Turing Machine
$\mathbf{NP}$完备性的是计算复杂性上一个至关重要的问题. 简而言之, $\mathbf{NP}$问题就是那些能够在确定多项式时间内被验证答案的判定问题, 即那些很容易就被检验的问题. $\mathbf{NP}$问题中, 有大量非常有现实意义但到现目前为止都没有好的解决办法的问题. 有关$\mathbf{NP}$完备性的讨论热度也从来没有衰减过.
2000年, 美国克雷数学研究所将$\mathbf{P}\overset{?}=\mathbf{NP}$列为七个千禧年大奖难题之一.
非确定计算模型
现在我们介绍一个计算模型. 该计算模型机的功能非常强大, 能够在多项式时间内求解很多我们尚未发现高效算法的问题.
非确定图灵机
非确定图灵机就像一台可以有无限个线程的计算机.
非确定图灵机(nondeterministic Turing machine, NDTM)与图灵机的定义大致相同. 不同的是, 非确定图灵机有两个转移函数, 每一步计算可以选择两个转移函数中的任何一个. 非确定图灵机物理上是不能实现的.
定义 非确定图灵机
一个非确定图灵机$N$是一个三元组$(\Gamma, Q, \delta=(\delta_1,\delta_2))$.
- 有限集$\Gamma$是字母表, 表示纸带可以记录的符号集.
- 有限集$Q$是状态集, 表示状态机的状态, 其中一个特殊的状态$q_\text{start}$为起始状态, $q_\text{accept}$为表示接受的停机状态, $q_\text{reject}$为表示拒绝的停机状态.
- $\delta_1,\delta_2: Q\times \Gamma^k\to Q\times \Gamma^{k-1}\times \{\text L,\text S,\text R\}^k$是两个转移函数
至于如何选择转移函数, 不是我们关心的问题, 因为我们非确定图灵机对问题的判定只关心计算路径.
非确定图灵机的中还有一点需要说的是, 非确定图灵机对一个语言的判定结果, 是从最终的停机状态进行输出的. 实际上我们也可以这样来定义图灵机, 但是 没有必要. 非确定图灵机之所以要这样定义, 是因为其判定一个语言的定义与图灵机有所不同. 在定义非确定图灵机判定一个语言之前, 我们首先定义计算分支.
非形式化地讲, 一台非确定图灵机$N$在特定输入$x$下, 计算过程中一条计算分支定义为从起始状态开始, 随机选择$\delta_1,\delta_2$进行计算, 直到$q_\text{accept}$或$q_\text{reject}$而停机. 这样一来, 每一种直到停机状态地$\delta_1,\delta_2$选择序列, 就对应一条计算分支. 这里地分支的描述已经很接近非确定自动机中的计算分支.
真正让非确定图灵机无法实现的是, 非确定图灵机停机和接受一个串的定义. 我们定义,
非确定图灵机$N$在$T(n)$时间内停机, 当且仅当对于任意的输入串$x\in\{0,1\}^\ast$, 无论$N$如何选择转移函数, 在$T(|x|)$时间内停机.
这里重申一下, 非确定图灵机的停机就是进入两个停机状态: $q_\text{accept}$或$q_\text{reject}$中的任意一个. 此外, 我们也可以将图灵机的输出也转换成用状态表示.
非确定图灵机$N$接受一个串$x$定义为, 输入$x$, 存在一个转移函数的选择方式, 使得$N$最终到达$q_\text{accept}$状态, 记作$N(x)=1$.
可以看出, 就这点来说, 物理上实现非确定图灵机就不太容易了. 非确定图灵机每一步计算, 就相当于是将一个线程分成了两个, 两个不同的转移函数选择各自对应一个子线程. 最终, 所有的线程中, 只要任何一个达到了$q_\text{accept}$就宣告图灵机接受该串. 还有一点需要注意的是, 我们这里并不要求图灵机每一条计算分支最终都会停机, 同时基于这一点, 我们可以通过如下方式定义非确定图灵机拒绝一个串.
非确定图灵机$N$拒绝一个串$x$定义为, 输入$x$, 至少存在一个转移函数选择方式使得$N$停机, 且当$N$停机时, $N$最终均将到达$q_\text{reject}$状态, 记作$N(x)=0$.
现在我们加上时间的限定, 给出非确定图灵机在$T(n)$时间内停机的定义.
非确定图灵机$N$在$T(n)$时间内停机, 如果对于任意输入$x\in\{0,1\}^\ast$, 无论$N$如何选择转移函数, 都会在$T(|x|)$时间内到达$q_\text{accept}$或$q_\text{reject}$状态.
也就是说, 我们要求$N$的每一条计算分支都在$T(|x|)$步就算内停机.
非确定图灵机的计算能力
首先我们说非确定图灵机$N$判定一个语言$L$可以被定义为$x\in L\iff N(x)=1$.
可以证明, 非确定图灵机和图灵机具有同样的计算能力[习题1], 我们不做过多的证明, 但是我们对非确定图灵机拒绝一个串的定义做一些讨论.
假设我们将非确定图灵机$N$拒绝一个串$x$定义为非确定图灵机$N$拒绝一个串$x$定义为, 输入$x$, 当$N$停机时, $N$最终均将到达$q_\text{reject}$状态. 假设有一台图灵机, 它的两个转移函数是一样的, 那么它就是一台图灵机, 那么对于一个判定$\mathbf{RE}$语言的图灵机$M$, 将它转换为一个两个转移函数均为$M$的转移函数的图灵机$N$, 那么$N$收到那些使得$M$不能停机的串$x$, 根据上述定义, 都应该有$N(x)=0$. 如果图灵机和非确定图灵机的计算能力相同, 也就有$\mathbf R=\mathbf{RE}$, 这显然是不正确的, 上述定义不是我们想要的.
非确定时间
$\mathbf{NTIME}$
设$T:\mathbb N\to \mathbb N$, 如果存在一台非确定图灵机$N$和一个常数$c$, 使得对于任意$x\in\{0,1\}^\ast$, $N(x)$在$cT(|x|)$时间内停机, 且对于任意$x\in L$, 有$N(x)=1$且, 则$L\in\mathbf{NTIME}(T(n))$.
实际上我们就是结合了图灵机在指定时间内停机的定义和图灵机判定一个语言$L$的定义, 我们要求
- 非确定图灵机所有分支均在指定时间内停机
- 非确定图灵机判定指定语言
$\mathbf{NP}$
现在, 我们定义一个非常重要的复杂性类, 它对于计算机复杂性理论的研究具有重大意义.
$\mathbf{NP}$
$$
\mathbf{NP}=\bigcup_{c\geq 1}\mathbf{NTIME}(n^c)
$$
用自然语言来叙述就是, $\mathbf{NP}$就是那些能够被一台非确定图灵机在多项式时间内判定的语言, 即
$$
L\in\mathbf{NP}\iff \exists c \exists i\forall x\in\{0,1\}^\ast:N_i(x)=1\leftrightarrow x\in L\text{ 且 }N_i在|x|^c\text{时间内停机}
$$
但从语言的描述, 没有接触过的同学可能不知道$\mathbf{NP}$问题意味着什么, 我们可以举一个简单的例子. 我们都知道判定一个数独的题目是否合法是困难的, 特别是在这个数独很大的时候. 但是对于非确定图灵机来说, 它只需要将这个数独填满再检查一遍这个答案是否通过即可. 由于每一条分支填写的答案不同(通过合理的编程即可容易地实现), 而且只要有一个分支是通过检查的就代表该数独题目确实有一个合法答案, 那这个题目也就是合法的. 对于一个输入规模为$n^2$的数独题目$x$来说, 每一条计算分支仅需要$O(n^2)$时间就可以完成猜测和检验, 因此整个问题输入$\mathbf{NP}$.
非确定通用图灵机
通用非确定图灵机(Nondeterministic Universal Turing Machine)类似于通用图灵机, 是一个可以模拟所有非确定图灵机运行的非确定图灵机. 同图灵机一样, 我们也可以对非确定图灵机进行编码, 将所有的非确定图灵机依次表示为
$$
N_0,N_1,N_2,\cdots
$$
我们将编码$i$和要判定的串$x$输出到非确定通用图灵机$\mathcal {V}$时, 非确定图灵机就会输出$\mathcal V(i,x)=N_i(x)$. 由于非确定图灵机具有”猜”的能力, 因此通用非确定图灵机的构造相对通用图灵机来说会相对容易一些, 我们采取的策略是先猜想后验证.
我们首先介绍快照(snapshot)的概念. 一条$k$带(非确定)图灵机的快照定义为
$$
\langle a_1,\cdots, a_k,q\rangle\in \Gamma^k\times Q
$$
其中$a_1,\cdots,a_k$为每条纸带上读写头的位置, 而$q$表示当前机器所处的状态. 我们在知道(非确定)图灵机的快照后, 就可以知道它在某一步按照某一个转移函数的转移方式. 假设现在给你一台处于某个状态的(非确定)图灵机, 让你验证它从当前的快照是否能够跳转到下一个快照, 需要多少时间?
首先, 我们要查看当前读写头的位置以及转移函数, 计算转移函数的结果, 然后根据转移函数的结果改写读写头处内容(虽然这一步与判定跳转的合法性无关, 但是可以维持我们的图灵机一直处在正确的计算步骤中), 转移读写头的位置和状态机的状态, 然后根据读写头的位置记录下读写头处的数据然后再和预期的快照进行匹配, 检查跳转是否正确. 整个过程都需要花费常数的时间.
现在我们来构造通用非确定图灵机$\mathbb V$. $\mathbb V$在收到输入$(i,x)$后, 每一步模拟计算, 首先猜想$N_i(x)$下一个计算步骤的快照, 再检验计算步骤的合法性, 再检查到非法的猜想或者$N_i(x)$停机时停机. 且仅在模拟$N_i(x)$计算时进入$q_{\text{accpte}}$状态时进入$q_{\text{accpte}}$状态.
假设$N_i(x)$需要$T$时间来完成计算, 由于猜想一个快照和检验当前状态的机器跳转到下一个快照(顺带维持机器的工作带)均只需要常数时间, 因此整个过程将$cT$时间内结束. 因此$\mathbb V$模拟一台$T(n)$时间内停机的非确定图灵机$N$仅需用时$cT(n)$, 其中$c$是某个常数.
如果你仔细思考就会发现, 相比通用图灵机, 这里之所以能节省出一个$\log T(n)$系数是因为我们不需要花时间来回地移动纸带. 在通用图灵机中, 我们花了大量的时间去维护存储空间. [习题2]
非确定时间谱系定理
待写.
$\mathbf{NP}$完备性
$\mathbf{NP}$的第二种定义
这一部分, 我们将从”证明”或”验证”的思想来陈述$\mathbf{NP}$问题. 一个比较惊奇的结果是, $\mathbf{NP}$也可以通过图灵机来进行定义.
$\mathbf{NP}$
$L$是$\mathbf{NP}$问题当且仅当存在一个多项式函数$p:\mathbb N\to\mathbb N$和一个多项式时间的图灵机$M$, 对于任意$x\in\{0,1\}^\ast$有
$$
x\in L\iff \exists u\in\{0,1\}^{p(|x|)}: M(x,u)=1
$$
并且称$u$是$x$在语言$L$中有关于$M$的一个认证(certificate, 或witness).
什么意思呢? 假设我们将一个语言$L$理解为一系列的真命题, 而所有的$\{0,1\}^\ast\backslash L$理解为假命题. 如果我们对所有的证明题都能给出一个(有关命题长度的)多项式长的证明, 且能够找到一台证明检验机器, 这台机器能够在多项式时间内完成证明的检验, 则称$L$是一个$\mathbf{NP}$问题. 这个解释有两个重要的要求:
- 证明不能太长
- 检验过程不能过于复杂
这是一种接近我们自然人思维的东西, 就像平时处理数学命题一样, 去证明一个命题也许需要一些创造性工作, 但是不长且合理的证明, 我们总是能够在很短的时间内完成验证.
回到我们刚才数独题目的合法性的例子, 如果有一台图灵机就是根据填入的答案的合理性来检查一个题目是否合法, 那么显然, 每一个合法的题目$x$, 其一个认证就是这个题目的答案.
定义中还有几个需要注意的地方:
- 定义中并没有要求每个$x\in L$只有一个认证, 也就是对于某个$x\in L$可能有$M(x,u)=1$, 也有$M(x,u’)=1$, 且两个认证都是多项式长的, 也都可以在多项式时间内完成验证.
- 定义中没有要求每个$x\notin L$有一个”认证”能帮助$M$快速地判定$M(x,u)=0$.
两种定义的等价性
我们用$\mathbf{NP}$表示第一种定义, 用$\mathbf{NP}$表示第二种定义, 我们来证明两种定义的等价性
$L\in$$\mathbf{NP}$$\Rightarrow$$L\in$$\mathbf{NP}$
设$L\in$$\mathbf{NP}$. 由于每个非确定图灵机$N$都是用一个图灵机$M$来代替, 并且将两个转移函数合并成一个. 用某个读写头的位置上的内容来表示下一步的计算使用哪个转移函数. 对于每个$x\in L$, 就可以直接用$N(x)$计算步骤中每一个接受分支的转移函数选择序列作为$M$上进行判断的认证. 同样对于每个$x\notin L$, 由于没有转移函数选择序列$u$使得$N(x)$某条计算分支接受, 因此$\forall u\in\{0,1\}^{\text{poly}(|x|)}: M(x,u)=0$. 因此$L\in$$\mathbf{NP}$.
$L\in$$\mathbf{NP}$$\Rightarrow$$L\in$$\mathbf{NP}$
假设$L\in$$\mathbf{NP}$, 则按照$L$定义中的符号$\exists u\in\{0,1\}^{\text{poly}(|x|)}: M(x,u)=1$. 我们可以构造这样一台非确定图灵机$N$, 它拿到$x$后首先进行$\text{poly}(|x|)$步骤的猜测, 然后再用$(x,u)$作为输入来模仿$M(x,u)$进行运算, 并输出$M(x,u)$. 显然$x\in L\iff \exists u\in\{0,1\}^{\text{poly}(|x|)}: M(x,u)=1\iff N(x)=1$. 由于$N$可以在多项式时间内停机, 因此$L\in$$\mathbf{NP}$.
$\mathbf{NP}$完备性
Karp归约
$\mathbf{NP}$完备问题
Cook-Levin定理
其他$\mathbf{NP}$问题
其他复杂度类
$\mathbf{coNP}$与$\mathbf{coNP}$完备性
$\mathbf{NEXP}$
高级论题
Ladner定理
Baker-Gill-Solovay定理
相对化
习题
- 解释[习题1]处计算能力的意思.
- 为什么通用非确定图灵机的构造中, 机器要猜测的其模拟机器的快照而不是格局?