计算理论基础 ​

问题 ​

语言 ​

一个 字母表（alphabet) 是一个非空有限集合，该集合中的元素称为 符号/字符（symbol)。

令 ${\mathrm{\Sigma }}^{\ast }$ 表示非负整数个 $\mathrm{\Sigma }$ 中的字符连接而成的串，字母表 $\mathrm{\Sigma }$ 上的一个 语言（language) 是 ${\mathrm{\Sigma }}^{\ast }$ 的一个子集。

需要注意的是，这里的「语言」是一个抽象的概念，通常意义上的字符串是语言，所有的有向无环图也可以是一个语言（01 串与有向图之间可以建立双射，具体方式无需了解）。

由于任何语言都可以转化成 01 串的形式，所以在下文中不加说明时 $\mathrm{\Sigma }=\{0,1\}$。

判定问题 ​

判定问题就是只能用 YES/NO 回答的问题，本质上是判定一个串是否属于一个语言，即：$f:{\mathrm{\Sigma }}^{\ast }\to \{0,1\},f(x)=1⟺x\in L$ 是一个关于字母表 $\mathrm{\Sigma }$ 和语言 $L$ 的判定问题。如，「判定一张图是不是一个有向无环图」就是一个判定问题。

判定问题由于其简洁性而常常被作为计算理论研究的对象。本文中不加说明时，「问题」都指「判定问题」，当然，有时一些命题也能简单地推广到其它问题上。

一个语言也可以代指「判定一个串是否属于这个语言」这个判定问题，因此，「语言」和「问题」可以视作同义词。

功能性问题 ​

功能性问题的回答不止 YES/NO，可以是一个数或是其它。如，「求两个数的和」就是一个功能性问题。

任何功能性问题都可以转化为一个判定问题，如，「求两个数的和」可以转化为「判定两个数的和是否等于第三个数」。

判定问题也可以转化为一个功能性问题：求这个判定问题的指示函数，即上文中判定问题定义里的 $f$。

图灵机 ​

确定性图灵机 ​

不加说明时，「图灵机」往往指「确定性图灵机」，本文中也是如此。

图灵机有很多不同的定义，这里选取其中一种，其它定义下的图灵机往往与下面这种定义的图灵机计算能力等价。

图灵机是一个在一条可双向无限延伸且被划分为若干格子的纸带上进行操作的机器，其有内部状态，还有一个可以在纸带上进行修改与移动的磁针。

正式地说，图灵机是一个七元组 $M=<Q,\mathrm{\Gamma },b,\mathrm{\Sigma },\delta ,q_0,F>$，其中：

• $Q$ 是一个有限非空的 状态集合；
• $\mathrm{\Gamma }$ 是一个有限非空的 磁带字母表；
• $b\in \mathrm{\Gamma }$ 是 空字符，它是唯一一个在计算过程中可以在磁带上无限频繁地出现的字符；
• $\mathrm{\Sigma }\subseteq (\mathrm{\Gamma }\setminus \{b\})$ 是 输入符号集，是可以出现在初始磁带（即输入）上的字符；
• $q_0\in Q$ 是 初始状态；
• $F\subseteq Q$ 是 接受状态，如果一个图灵机在某个接受状态停机，则称初始磁带上的内容被这个图灵机 接受。
• $\delta :(Q\setminus F)\times \mathrm{\Gamma }\nrightarrow Q\times \mathrm{\Gamma }\times \{L,R\}$ 是一个被称作 转移函数 的 partial function（即只对定义域的一个子集有定义的函数）。如果 $\delta$ 在当前状态下没有定义，则图灵机停机。

图灵机从初始状态与纸带起点起，每次根据当前的内部状态 $x$ 和当前磁针指向的纸带上的单元格中的字符 $y$ 进行操作：若 $\delta (x,y)$ 没有定义则停机，否则若 $\delta (x,y)=(a,b,c)$，则将内部状态修改为 $a$，将磁针指向的格子中的字符修改为 $b$，若 $c$ 为 $L$ 则向左移动一格，为 $R$ 则向右移动一格。

其实，知道图灵机的工作细节是不必要的，只需建立直观理解即可。

图灵机 $M$ 在输入 $x$ 下的输出记作 $M(x)$（$M(x)=1$ 当且仅当 $M$ 接受 $x$，$M(x)=0$ 当且仅当 $M$ 在输入 $x$ 下在有限步骤内停机且 $M$ 不接受 $x$），也可以在括号内包含多个参数，用逗号隔开，具体实现时可以向字母表中添加一个元素表示逗号来隔开各个参数。

图灵机与冯·诺依曼计算机解决问题的时间复杂度差别在多项式级别内，所以研究复杂度类时可以使用图灵机作为计算模型。

非确定性图灵机 ​

非确定型图灵机是图灵机的一种，它与确定型图灵机的不同在于：确定型图灵机的每一步只能转移到一个状态，而非确定型图灵机可以「同时」转移到多个状态，从而在多个「分支」并行计算，一旦这些「分支」中有一个在接受状态停机，则此非确定性图灵机接受这个输入。

事实上，任何确定型图灵机都可以用类似于迭代加深搜索的方式在指数级时间内模拟一台非确定型图灵机多项式时间内的行为。

在现实生活中，确定型图灵机相当于单核处理器，只支持串行处理；而非确定型图灵机相当于理想的多核处理器，支持无限大小的并行处理。

可计算性 ​

不可计算问题 ​

对于一个判定问题，若存在一个总是在有限步内停机且能够正确进行判定的图灵机，则这个问题是一个 图灵可计算 的问题，否则这个问题是一个 图灵不可计算 的问题。

由于图灵机可以被自然数编码，所以图灵机的个数是可数无穷，而语言（即二进制串的集合）的个数是不可数无穷，而每个图灵机最多判定一个语言，所以一定存在图灵不可计算的问题。

停机问题 ​

停机问题是一个经典的图灵不可计算问题：给定 $\alpha$ 和 $x$，判定 $M_{\alpha }$ 在输入为 $x$ 时是否会在有限步内停机。

复杂度类 ​

复杂度类有很多，本文只会介绍其中较为常见的一小部分。

DTIME ​

如果存在一台确定性图灵机能够判定一个语言，且对于任何输入 $x$，这台图灵机可以在 $O(f(|x|))$ 的时间内停机，那么这个语言属于 $\mathsf{DTIME}(f(n))$ 类。

P ​

复杂度类 $\mathsf{P}$ 表示可以由确定性图灵机在多项式时间内解决的判定问题，即：

线性规划、计算最大公约数、求图的最大匹配的判定版本都是 $\mathsf{P}$ 类问题。

EXPTIME ​

复杂度类 $\mathsf{EXPTIME}$ 表示可以由确定性图灵机在指数级时间内解决的判定问题，即：

停机问题的弱化版——给定一个图灵机的编码以及一个正整数 $k$，判定这个图灵机是否在 $k$ 步内停机，是一个 $\mathsf{EXPTIME}$ 类的问题。因为这个问题的解法需要 $O(k)$ 的时间，而数字 $k$ 可以被编码为长度为 $O(\log k)$ 的二进制串。

NTIME ​

如果存在一台非确定性图灵机能够判定一个语言，且对于任何输入 $x$，这台图灵机可以在 $O(f(|x|))$ 的时间内停机，那么这个语言属于 $\mathsf{NTIME}(f(n))$ 类。

NP ​

复杂度类 $\mathsf{NP}$ 表示可以由非确定性图灵机在多项式时间内解决的判定问题，即：

所有 $\mathsf{P}$ 类问题都是 $\mathsf{NP}$ 类问题。更多 $\mathsf{NP}$ 类问题请参见下文中的 NPC 问题以及 NP-intermediate 问题。

NP-hard ​

如果所有 $\mathsf{NP}$ 类问题都可以在多项式时间内规约到问题 $H$，那么问题 $H$ 是 NP-hard 的。

换句话说，如果可以在一单位的时间内解决 NP-hard 的问题 $H$，那么所有 $\mathsf{NP}$ 类问题都可以在多项式单位的时间内解决。

NP-complete ​

如果一个问题既是 $\mathsf{NP}$ 类问题又是 NP-hard 的，那么这个问题是 NP 完全 (NP-complete) 的，或者说这是一个 NPC 问题。

一些经典的 NPC 问题：旅行商问题的判定版本、最大独立集问题的判定版本、最小点覆盖问题的判定版本、最长路问题的判定版本、0-1 整数规划问题的判定版本、集合覆盖问题、图着色问题、背包问题、三维匹配问题、最大割问题的判定版本。

NPC 问题的功能性版本往往是 NP-hard 的，例如：「判定一张图中是否存在大小为 $k$ 的团」既是一个 $\mathsf{NP}$ 类问题又是 NP-hard 的，从而它是一个 NPC 问题，而它的功能性版本「求一张图的最大团」不是 NPC 问题，但这个功能性版本依然是 NP-hard 的。

类似地，其它复杂度类也会有「XX-complete」，如所有 $\mathsf{EXPTIME}$ 类的问题都能在多项式时间内规约到 EXPTIME-complete 的问题。

NP-intermediate ​

如果一个问题是 $\mathsf{NP}$ 类问题，但它既不是 $\mathsf{P}$ 类问题也不是 NPC 问题，则称其为 NP-intermediate 问题。

就人们目前的了解，图同构问题、离散对数问题和因数分解问题可能是 NP-intermediate 的。

Ladner 定理指出，如果 $\mathsf{P}\ne \mathsf{NP}$，则一定存在问题是 NP-intermediate 的。

NEXPTIME ​

复杂度类 $\mathsf{NEXPTIME}$ 表示可以由非确定性图灵机在指数级时间内解决的判定问题，即：

复杂度类之间的关系 ​

P?=NP ​

复杂度类 $\mathsf{P}$ 与 $\mathsf{NP}$ 是否相等是计算复杂度理论中一个著名的尚未解决的问题。

若 $\mathsf{P}=\mathsf{NP}$，可以得到 $\mathsf{NP}=\mathsf{co}\mathsf{-}\mathsf{NP}$，但反之不行（目前没有基于 $\mathsf{NP}=\mathsf{co}\mathsf{-}\mathsf{NP}$ 证明 $\mathsf{P}=\mathsf{NP}$ 的方法）。

若 $\mathsf{P}=\mathsf{NP}$，还可以得到 $\mathsf{EXPTIME}=\mathsf{NEXPTIME}$。

若 $\mathsf{P}\ne \mathsf{NP}$，可以得到 NP-intermediate 不为空。

参考资料 ​

1. 计算复杂性（1）Warming Up: 自动机模型；

2. 计算复杂性（2）图灵机计算模型；

3. Wikipedia 的相关词条以及这些词条的参考资料。