

计算理论基础

本部分将介绍基础的计算理论的知识。

语言

设 $\sigma$ 是一个字符集。 $\sigma$ 上的所有的串构成集合 $\sigma^*$ 。称字母表 $\sigma$ 上的语言 $L$ 就是 $\sigma^*$ 的一个子集。非形式化来说，语言就是字符串的集合。

图灵机、可判定性与丘奇 - 图灵论题

如果你已经知道图灵机在计算复杂性上和普通计算机多项式地等价的话，那么可以跳过这一段。

图灵机

注

如果不加特殊说明，通常所说的图灵机都是确定型图灵机。

非形式化地说，图灵机包含一个有限状态机、一条两端无限长的纸带和一个指针。图灵机的每一步操作包括一次状态转移和一次指针移动。采用何种操作的依据是当前的状态以及指针指向的字符。一般情况下输入位于图灵机的纸带上，而指针初始位置指向输入字符串的开头。形式化地，一个图灵机是七元组 $M=(Q,\sigma, \gamma, \delta, q_0, B, F)$ ，其中

1. $Q$ 是状态机的状态集合。
2. $\sigma$ 是字符集。
3. $\gamma$ 是带符号的集合，且 $\sigma$ 是 $\gamma$ 的真子集。一般取 $\gamma = \sigma \cup \{ B \}$ ， $B$ 的含义后述。
4. $\delta(q, X)$ 是转移函数。其中参数 $q\in Q$ 是有限状态机的一个状态， $X\in \gamma$ 是带符号。转移函数的输出可能为一个三元组 $(q', X', D)$ ，也可能直接使图灵机停机，其中 $q'\in Q$ 为下一状态， $X'\in\gamma$ 为向当前指针指向的格子中填入的字符， $D$ 是写下新字符以后指针移动的方向，一般取 $D$ 为向左一格、向右一格、不动这三个选择。
5. $q_0$ 是状态机的初始状态。
6. $B$ 是空格符号。这一符号不在字符集中，但是在带符号之中。开始时，除了输入串外，纸带上每个格子都是 $B$ 。
7. $F$ 是状态机的终结状态构成的集合。

称图灵机 $M$ 接受一个字符串 $s$ ，如果 $M$ 最终达到接受态并停机，记 $M(s) = 1$ 。称图灵机 $M$ 拒绝一个字符串 $s$ ，如果 $M$ 已停机但未停在接受态，记 $M(s) = 0$ 。注意，对于某些串，图灵机可能永不停机，也就是说 $\{s:M(s)=1\}\cup\{s:M(s)=0\}$ 有可能不是全集。记所有 $M$ 接受的串构成的语言为 $L(M)$ 。称图灵机 $M$ 判定语言 $L$ ，如果 $L=L(M)$ ，且对于任意 $s\notin L$ ，都有 $M(s) = 0$ 。

可判定性

一个语言称为递归可枚举的，如果存在一个图灵机接受它。一个语言 $L$ 被称为可判定的（递归的），如果存在一个图灵机判定它。注意递归的语言都是递归可枚举的语言，反之不然（由于历史原因而产生这个可能导致误解的命名）。

丘奇 - 图灵论题

（挖坑）

非确定型图灵机

非确定型图灵机是图灵机的一种，它与确定型图灵机最大的不同在于：确定型图灵机的每一步只能转移到一个状态，状态转移方式近似于 DFS；非确定型图灵机可以并行转移到多个状态，状态转移方式近似于 BFS。事实上，任何确定型图灵机都可以用类似于迭代加深搜索的方式在 $\Theta(w^n)$ 内模拟一台非确定型图灵机 $\Theta(n)$ 内的行为。

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

复杂度类 P、NP、coNP 与 NPC

P 类问题指可以由确定性图灵机在多项式时间内判定的问题，包括寻找最值 $\Theta(n)$ ，序列排序 $\Theta(n\log n)~\Theta(n^2)$ 等。

NP 类问题指可以由非确定性图灵机在多项式时间内判定的问题（同时可以用确定性图灵机在多项式时间内判定答案正确性），包括质因数分解问题，01 整数线性规划等。

coNP 类问题与 NP 类问题相反：NP 类问题是可以快速判断答案是否 正确 的一类问题，而 coNP 类问题是可以快速判断答案是否 错误 的一类问题。

在 NP 类问题中，有一类问题比较特殊，他们能够在多项式时间内转化为任何一个 NP 问题（包括其他同类问题），这类问题被称为 NPC 问题，其中较为有名的有 21 个：

• SAT 问题：0-1 整数规划、最小顶点覆盖问题、集合覆盖问题、分团问题、集合覆盖问题等

• 3-SAT 问题：图着色问题、分团覆盖问题、三维匹配问题、背包问题、最大割、划分问题等

显而易见的是，P 类问题一定既是 NP 问题，也是 coNP 问题（可以直接计算结果来与答案比较），但 P=NP? 是一个 尚未解决 的问题。

Karp 归约、Cook-Levin 定理

（大坑）

经典问题所在的复杂性类

（大大坑）

其它复杂度类

（大坑）

概率图灵机与随机复杂性类

（大坑）

空间复杂性类

在计算机科学中，算法或程序的空间复杂度指用来解决问题所需要的内存总量与输入数据大小的函数关系。

（大坑）

你知道吗？

下面是一些关于复杂性理论的有意思的结果（随时补充）。

1. 时间层次定理： $\mathbf{DTIME}(o(\frac{f(n)}{\log f(n)}))$ 是 $\mathbf{DTIME}(f(n))$ 的真子集。一个直接的结论就是 $\mathbf{P}\neq\mathbf{EXP}$ 。
2. 如果 $\mathbf{P}\neq\mathbf{NP}$ ，那么存在一个 NP 问题，它既不在 P 中，也不是 NP 完全的。（Ladner 定理）
3. 如果图同构问题的判定版本是 NP 完全的，那么 PH（多项式层级）会坍塌，而人们不相信 PH 会坍塌。
4. MAX-3SAT 问题（尽可能满足数量多的子句）不存在 $\frac{7}{8}+\varepsilon$ 近似比的多项式时间算法，除非 $\mathbf{P}=\mathbf{NP}$ 。这个定理是 1997 年才被证明的。（Hastad 的 PCP 定理）
5. 虽然人们不知道是否有 $\mathbf{P}\neq\mathbf{NP}$ ，但人们知道 $\mathbf{PSPACE}=\mathbf{NPSPACE}$ 。（Savitch 定理）
6. 不存在多项式时间的算法统计一个二部图完美匹配的数量，除非 $\mathbf{P}=\mathbf{NP}$ 。这是一个判定版本（二部图有没有完美匹配？）与计数版本（有多少完美匹配？）计算复杂性相差悬殊的例子。

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论