除了能够设计求解问题的算法以外，还需要具备基本的计算理论，了解哪些问题是可计算的、哪些问题是不可计算的。这里从图灵机模型开始，简要介绍计算复杂性理论。

---

11.1 计算模型

11.1.1 求解问题的分类

算法呈现不同的时间复杂度，有的属于多项式复杂度算法，有的属于指数级复杂度算法，通常将存在多项式时间算法的问题看作易解问题，将需要指数时间算法解决的问题看作难解问题。

归纳起来，各种求解问题按算法的时间复杂度可分为三大类：第一类是存在多项式算法的问题，第二类是肯定不存在多项式算法的问题，第三类是尚未找到多项式算法、也不能证明其不存在多项式算法的问题。第三类问题介于第一类问题和第二类问题之间。

随着计算科学理论的发展，第三类问题将逐步向第一类和第二类分化。第三类问题中有一个子类，这个子类的问题之间有着非常密切的联系，或者全体转换为第一类问题，或者全体转化为第二类问题。至今为止，已经知道属于这个子类的问题有数千个，而且还在不断增加，这个子类就是后面讨论的 NPC 问题（NP 完全问题）。为了准确地描述 NPC 问题，需要有关图灵机的概念。

11.1.2 图灵机模型

图灵机 Turing machine 是于1936年由英国数学家 A. M. Turing 提出的一种计算模型。图灵机模型的基本结构包括：一条向右无限延伸的输入带（可读可写）、一个有限状态控制器、连接控制器和输入带的读写头。图灵机的输入带由一个个格子组成，每一格可以存放一个字符，如图11.1所示。

但图灵机的读写头扫描到一个格的字符时，根据控制器的当前状态和扫描到的字符，决定图灵机的动作，包括 $3$ 个方面，即控制器进行状态转换（决定下一状态）、读写头在当前格上写上新的字符、决定读写头向左或向右移动一格。

图灵机分为确定性图灵机和非确定性图灵机两种。

1. 确定性图灵机

确定性图灵机 deterministic Turing machine, DTM 的定义如下：图灵机是一个七元组 $$M=(Q,q_0,F,\Gamma ,B,\Sigma ,\delta )$$ 其中 $Q$ 是有限状态集、$q_0(q_0\in Q)$ 是初始状态、$F(F\subseteq Q)$ 是终止状态集，$\Gamma$ 是输入带的符号集，$B(B\in \Gamma )$ 是空白符，$\Sigma$ 是 $\Gamma$ 中除 $B$ 以外的输入字母表。 δ :   Q × Γ → Q × Γ × { L , R } \delta:\ Q \times \Gamma \to Q \times \Gamma \times \{ L, R\} δ: Q×Γ→Q×Γ×{L,R} 是动作函数，其中 $L$ 表示左移一格、$R$ 表示右移一格，对于某些 $q\in Q$ 和 $a\in \Gamma$ ，$\delta (q,a)$ 可以无定义。

与「人在日常中用笔纸计算以及计算机」进行类比，输入带起着纸的作用，相当于计算机中存储器的角色，读写头其中人的眼和手的作用，也起着计算机中运算器、寄存器和输出设备所起的作用；控制器和人的大脑、计算机的CPU有着相似的地位。

图灵机 $M$ 的工作过程是这样的：

1. 把输入串 $a_1{a}_2\dots a_n(a_i\in \Sigma )$ 放置在输入带上，例如放置在最左端；
2. 开始时读写头注视输入带上的某一格，如注视最左端的第一格（开始时读写头可以注视输入带上的任一格），$M$ 的初始状态为 $q_0$ 。
3. 在每一步，读写头把扫描到的字符（设为 $x_i$ ）传送到有限状态控制器；
4. 有限状态控制器根据当前状态 $q$ 和动作函数 $\delta (q,x_i)$ 确定状态的变化，在当前格上写上新字符、以及移动读写头；
5. 当进入某个终止状态或 $\delta (q,x_i)$ 无定义时，图灵机 $M$ 停机。

用符号 $\to$ 表示推导关系，$\stackrel{\ast }{\to }$ 表示多步推导。设当前瞬像为 $x1\dots x_{i-1}q{x}_i\dots x_n$ ，表示当前状态为 $q$ ，读写头正注视着 $x_i$ 字符。注意：

• 若 $\delta (q,x_i)=(p,y,L)$ ，则 $i=1$ 时不能进行下一步推导（读写头无法向左移）；
• 当 $i>1$ 时有：$$x_1\dots x_{i-1}q{x}_i\dots x_n\to x_1\dots x_{i-2}p{x}_{i-1}y{x}_{i+1}\dots x_n$$ 即将 $x_i$ 改为 $y$ 、读写头左移一格并注视 $x_{i-1}$ 字符、状态变为 $p$ 。
• 若 $\delta (q,x_i)=(p,y,R)$ ，则有：
  $$x_1\dots x_{i-1}q{x}_i\dots x_n\to x_1\dots x_{i-1}yp{x}_{i+1}\dots x_n$$ 即将 $x_i$ 改为 $y$ 、读写头右移一格并注视 $x_{i+1}$ 字符、状态变为 $p$ 。

对于图灵机 $M$ ，能够从初始状态出发、最终到达某个终止状态的输入串，就是该图灵机所接受的符号串，所有这样的符号串构成的集合称为该图灵机所接受的语言。

【例11.1】设计一个图灵机 $M$ ，它接受的语言 L = { 0 n 1 n ∣ n > 1 } L = \{ 0^n 1^n \mid n > 1\} L={0n1n∣n>1} ，构造该图灵机。
解：假设输入串 $w$ 为 $00\dots 011\dots 1\text{BB}\dots$（$B$ 为空白符），设计出来的图灵机的主要功能是检查 $0$ 的个数和 $1$ 的个数是否相等。使读写头往返移动，每往返一次就成对地对输入符号串 $w$ 左端的一个 $0$ 和右端的第一个 $1$ 做标记。

• 如果恰好把输入串的全部符号都做了标记，说明左边的符号 $0$ 和右边的符号 $1$ 的个数相等，则 $w\in L$ 。
• 或者左边的 $0$ 已全部标记、右边还有若干 $1$ 没有标记；或者右边的 $1$ 已全部标记、左边还有若干 $0$ 没有标记，这说明左边的符号 $0$ 和右边的符号 $1$ 的个数不等；或者 $0$ 与 $1$ 交替出现，则 $w\notin L$ 。

该图灵机 $M$ 的工作过程为：

• 首先用 $x$ 替换输入带最左边的 $0$ ，再右移（余下的 $0$ 或 $y$ 暂时不修改）至最左边的 $1$ 并用 $y$ 替换之，然后左移（遇到 $0$ 或 $y$ 暂时不修改）寻找最右边的 $x$ ，然后右移一单元到最左边的 $0$ ，重复这一循环。
• 如果在寻找 $1$ 时 $M$ 找到了空白符 $B$ ，则 $M$ 停止，不接受该串（此时 $0$ 的个数大于 $1$ 的个数）；
• 如果将 $1$ 改为 $y$ 后左边再也找不到 $0$ ，此时若右边再无 $1$ ，接受；若仍有 $1$ ，则 $1$ 的个数大于 $0$ 的个数，不接受。

例如，识别输入串 $w_1=0011$ 的过程如图11.2所示。

该图灵机 $M$ 对应的状态转换图，如图11.3所示。其中结点表示状态，结点内的 $L,R$ 表示读写头的移动方向，边上的标记 $x/y$ 表示该读写头原来注视的符号 $x$ 改为 $y$ 。

为此，在图灵机的输入带符号中除了 $0,1,\text{B}$ 以外，还应有 $x,y$ 。为实现上述功能，图灵机应该设置 $5$ 个状态。

1. $q_0$ ：初始状态；
2. $q_1$ ：在 $q_0$ 下读到 $0$ ，把 $0$ 改为 $x$ ，同时状态改为 $q_1$ ，向右移。在 $q_1$ 下读到 $0$ 或 $y$ ，不改动，继续右移，直到读到 $1$ ，状态改为 $q_2$ 。
3. $q_2$ ：在 $q_1$ 下读到 $1$ ，把 $1$ 改为 $y$ ，同时状态改为 $q_2$ ，向左移。在 $q_2$ 下读到 $0$ 或 $y$ ，不改动，继续左移，直到读到 $x$ ，状态改为 $q_0$ 。
4. $q_3$ ：在 $q_0$ 下读到 $y$ ，状态改为 $q_3$ 。
5. $q_4$ ：在 $q_3$ 下读到 $\text{B}$ ，状态改为 $q_4$ ，$q_4$ 为终止状态。

对应的动作函数 $\delta$ 设计如下：
$$\begin{array}{rl}& \delta (q_0,0)=(q_1,x,R),\delta (q_0,y)=(q_3,y,R)\\ & \delta (q_1,0)=(q_1,0,R),\delta (q_1,y)=(q_1,y,R),\delta (q_1,1)=(q_2,y,L)\\ & \delta (q_2,0)=(q_2,0,L),\delta (q_2,y)=(q_2,y,L),\delta (q_2,x)=(q_0,x,R)\\ & \delta (q_3,y)=(q_3,y,R),\delta (q_3,B)=(q_4,B,R)\end{array}$$

采用表格形式描述的动作函数 $\delta$ ，如表11.1所示。

识别输入串 $w_1=0011$ 的瞬像演变过程如下：
$$\begin{gathered} q_{0}0011\to x{q}_{1}011\to x0q_{1}11\to x{q}_{2}0y1\to q_{2}x0y1\to \\ x{q}_{0}0y1\to xx{q}_{1}y1\to xxy{q}_{1}1\to xx{q}_{2}yy\to x{q}_{2}xyy\to \\ xx{q}_{0}yy\to xxy{q}_{3}y\to xxyy{q}_{4}B\to xxyyB{q}_4 \end{gathered}$$

进入终止状态 $q_4$ ，图灵机 $M$ 停机、并接受输入串 $w_1$ 。

识别输入串 $w_2=011$ 的瞬像演变过程如下：
$$q_{0}011\to x{q}_{1}11\to q_{2}xy1\to x{q}_{0}y1\to xy{q}_{3}1$$

由于 $\delta (q_3,1)$ 无定义，而 $q_3$ 不属于终止状态，所以停机但不接受 $w_2$ 。

图灵机不仅可以作为语言识别器，还可以计算函数。

【例11.2】设计一个图灵机，实现下面函数的计算：
$$f(m,n)=\{\begin{array}{ll}m-n& 当m\ge n时\\ 0& 当m<n时\end{array}$$
解：输入带上的初始信息如下。

在输入带上，用连续 $m$ 个 $0$ 表示整数 $m$ ，$m$ 、$n$ 的各数之间用 $1$ 隔开。实现这个函数计算的图灵机为 M = ( Q ,   q 0 ,   Φ ,   { 0 , 1 , B } ,   B ,   { 0 , 1 } ,   δ ) M = (Q,\ q_0,\ \Phi ,\ \{0, 1, B\},\ B,\ \{0, 1\},\ \delta) M=(Q, q0​, Φ, {0,1,B}, B, {0,1}, δ) ，其中 Q = { q 0 , q 1 , q 2 , q 3 , q 4 , q 5 , q 6 } Q = \{ q_0, q_1, q_2, q_3, q_4, q_5, q_6 \} Q={q0​,q1​,q2​,q3​,q4​,q5​,q6​} ，动作函数 $\delta$ 如表11.2所示。

例如输入串为 $0010$ ，其瞬像演变过程如下：
$$\begin{gathered} q_{0}0010\to B{q}_{1}010\to B0q_{1}10\to B01q_{2}0\to B0q_{3}11\to \\ B{q}_{3}011\to q_{3}B011\to B{q}_{0}011\to BB{q}_{1}11\to BB1q_{2}1\to \\ BB11q_{2}B\to BB1q_{4}1\to BB{q}_{4}1B\to B{q}_{4}BBB\to B0q_{6}BB \end{gathered}$$

前面定义的图灵机只有一条输入带，其实也可以有多条输入带，称之为多带图灵机。$k(k\ge 1)$ 带图灵机有 $k$ 条输入带和 $k$ 个读写头，但只有一个有限状态控制器，它扫描 $k$ 条输入带上的当前格的信息，才能决定图灵机的动作。

人们证明过，多带图灵机在识别语言和计算函数方面的能力和单带图灵机是等价的。一个语言（函数）能被一个多带图灵机接受（计算），当且仅当它能被一个单带图灵机接受（计算）。

2. 非确定性图灵机

非确定性图灵机 non deterministic Turing machine, NDTM 和确定性图灵机的区别在于它的动作函数 $\delta$ 是一个多值映射，即在一个状态下、扫描到带上一格的字符、可以产生多个动作，包括状态的变化、在当前格上写上新的字符、以及读写头的左/右移动。即一个动作函数可以表示为：
$$\delta (q,a)=\{\begin{array}{l}(q_1,b_1,A_1)\\ (q_2,b_2,A_2)\\ \dots \\ (q_k,b_k,A_k)\end{array}$$

其中，$A_i(1\le i\le k)$ 表示移动方向，取 $L$ 或 $R$ 。

例如，图灵机 $M=(Q,q_0,F,\Gamma ,B,\Sigma ,\delta )$ 。其中 $q_0$ 是初始状态，$q_1$ 是终止状态，动作函数 $\delta$ 如下：
$$\begin{gathered} \delta (q_0,B)=(q_0,1,R),\delta (q_0,B)=(q_0,B,L) \\ \delta (q_0,B)=(q_1,B,R),\delta (q_0,1)=(q_0,1,L) \end{gathered}$$

它是一个不确定图灵机，可以对输入的空带写下任意长的一段后停机。

从中看出，对于一个输入串而言，可能存在着若干个演变过程，其中任何一个演变过程最后导致一个终止状态，则这个输入串就被非确定性图灵机接受。同样也可以定义多带非确定性图灵机。

对于任意一个非确定性图灵机 $M$ ，存在一个确定性图灵机 $M^{\prime }$ ，使得它们的语言相等，即 $L(M)=L(M^{\prime })$ 。

3. 图灵机的停机问题和可计算性度量

一个图灵机并不是对任何输入都能停机。一般来说，一个图灵机 $M$ 对一个输入串 $w$ 的工作过程可能遇到 $3$ 种情况：
（1）进入终止状态，这时 $M$ 停机，并接受 $w$ ;
（2）未进入终止状态，但 $\delta$ 无定义，此时 $M$ 停机，但不接受 $w$ ；
（3）一直不进入终止状态，且 $\delta$ 一直有定义，这时进入死循环，$M$ 永不停机。

可计算函数和可计算语言的定义，与图灵机的停机问题有密切的联系——若一个语言被一个图灵机 $M$ 接受，且对任意输入串 $w$ 、$M$ 都停机，称之为递归语言。一个语言是可计算的，当且仅当它是一个递归语言。同样的，一个函数是可计算的，当且仅当它是完全递归函数，即存在图灵机 $M$ 实现其计算功能，且对于任意输入，$M$ 都能停机。

从根本上来说，一个算法就是一个确定的、对任意输入都停机的图灵机。

---

11.2 P 类和 NP 类问题

确定性图灵机是现代电子计算机的理论模型。一个对任意输入都停机的确定性图灵机在多项式时间内可解的问题，必然存在多项式时间复杂度的计算机求解算法。一个算法实质上就是一个以任何输入都停机的（确定性）图灵机，因此已经找到了多项式时间界的计算机算法（是确定性图灵机！）的问题，都属于 P 类问题。

非确定性图灵机只是一种理论上的计算模型。非确定性图灵机可解的问题，虽然也可以用确定性图灵机求解，但时间上的耗费（或者说求解步数）是不一样的。用非确定性图灵机、以多项式时间界可求解的问题，用确定性图灵机不能保证在多项式时间界内可求解，但用确定性图灵机、以指数时间界是肯定可以求解的。至于非确定性图灵机都不可解的问题呢？

用确定性图灵机、以多项式时间界可解的问题，称为 P 类问题，Polynomial, P 指确定性图灵机上的、具有多项式算法的问题集合。用非确定性图灵机、以多项式时间界可解的问题，称为 NP 问题，Nondeterministic Polynomial, NP 指非确定性图灵机上的、具有多项式算法的问题集合。

确定性图灵机可以看作是非确定性图灵机的一种特殊情况，因此这两个问题集合之间存在子集关系，即 $P\subseteq NP$ 。现在的问题是 P 是 NP 的真子集吗？换个说法，用非确定性图灵机、以多项式时间界可求解的问题，也都存在多项式时间界的确定性图灵机求解算法吗？

脱离图灵机的概念，在普通的计算机上看，P 问题是指能够在多项式时间内求解的判定问题（判定问题指只需要回答是和不是的问题），NP 问题则是指那些肯定解能够在给定的正确信息下、在多项式时间内验证的判定问题，但不肯定「解不能够在多项式时间内得出结果」的判定问题（？）。

例如，以下问题都是 P 问题：

1. 最短路径判定问题：给定带权有向图 $G=(V,E)$ ，权值为正整数，判定是否存在从顶点 $s$ 到顶点 $t$ 的、长度小于 $l$ 的最短路径（$s,t$ 为 $V$ 中的顶点，$l$ 为正整数）。
2. 排序判定问题：给定 $n$ 个整数的序列，判定是否可以递增排序。

实际上，$P=NP?$ 这个问题作为理论计算机科学的核心问题，其声名早已超越了这个领域。它是 Clay 研究所的 $7$ 个百万美元大奖问题之一，在2006年国际数学家大会上它是某个 $1$ 小时讲座的主题。

NP 问题的代表问题之一是旅行商问题，即一个售货员要到 $n$ 个指定的城市去推销货物，他必须经过全部的 $n$ 个城市，现在他有这 $n$ 个城市的地图、及各城市之间的距离，试问他应如何取最短的行程，从家中出发再回到家中？第9章的各种求解算法的时间复杂度均为 $O(nn!)$（用贪心法不一定能得到正确的解）。

目前发现的 NP 问题还有很多，如布尔表达式的可满足性问题、图的顶点覆盖问题和背包问题等。

---

11.3 NPC 问题

NP-completeness, NPC 的概念表明：找到某个问题的有效算法，至少和找 NP 中所有问题的有效算法一样难。这里的有效性是指为求解问题设计的算法的时间为多项式级的。下面给出多项式归约的定义。

设 $L_1\subseteq {\sum }_1^{\ast },L_2\subseteq {\sum }_2^{\ast }$ 为两个语言，若存在映射 $f:{\sum }_1^{\ast }\to {\sum }_2^{\ast }$ ，使得：
（1）存在多项式时间界的确定图灵机求解 $f$ ；
（2）$\forall x\in {\sum }_1^{\ast },x\in L_1\iff f(x)\in L_2$ 则称 $L_1$ 可以多项式归约为 $L_2$ ，记为 $L_1\propto L_2$ 。例如，有向哈密尔顿回路问题可多项式归约为旅行商问题。

容易证明，多项式归约具有以下性质：

• $Q_1\in P$ ，若 $Q_2\propto Q_1$ ，则 $Q_2\in P$ 。
• 若 $Q_1\propto Q_2$ ，且 $Q_2\propto Q_3$ ，则 $Q_1\propto Q_3$ 。

设 $Q_1$ 为一个问题，若对任意问题 $Q\in NP$ 都有 $Q\propto Q_1$ ，则称问题 $Q_1$ 为 NP-hard 的。NP 困难问题可以说是比任一个 NP 问题都不会“更容易”求解的问题。

设 $Q_1\in NP$ ，若 $\forall Q\in NP$ 都有 $Q\propto Q_1$ ，则称 $Q_1$ 为一个 NPC 问题（NP 完全问题）。显然，NPC 问题是 NP 问题的一个子集，且 NPC 问题属于 NP-hard 问题。

若 $Q\in NPC$ ，那么 $NP=P$ 当且仅当 $Q\in P$ 。尽管这时很显然的，它却表述了计算复杂性理论中的一个非常重要的结论。这一结论把瞩目的 $NP=P?$ 的问题转化为这样的工作：或者对一个 NPC 问题寻找多项式时间界的求解算法，或者证明某个 NPC 问题肯定不存在多项式时间界的算法。只要对其中一个 NPC 问题找出多项式时间界的求解算法，那么所有的 NPC 问题都存在多项式时间界的求解算法，从而就有 $NP=P$。反之，如果证明了其中一个 NPC 问题不存在多项式时间界的求解算法，则有 $NP\ne P$ 。P 类问题、NP 类问题和 NPC 问题的关系如图11.4所示。

1971年，S. A. Cook 证明布尔表达式的可满足性问题是一个 NPC 问题，从而肯定地回答了 NPC 问题的存在性。随后，人们通过多项式归约、找出了许多 NPC 问题，并证明了：任一 NP 问题都可以多项式归约为布尔表达式的可满足性问题。

归纳起来，NP 问题包含 P 问题和 NPC 问题，目前属于多项式时间界求解的问题都属于 P 问题，NPC 问题是 NP 问题中最难的问题，目前尚不能确定能否用多项式时间界算法来求解。但已证明：如果 NPC 问题中有一个问题能用多项式时间界算法求解，则所有 NPC 问题都可用多项式时间界算法求解。例如，旅行商问题可被证明具有 NPC 计算复杂性，因此任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

---

其他问题