自动人形会梦见 NP 完全问题吗？

Posted on 2024-08-16 繁/简： set

计算理论 (Theory of Computation) 当之无愧是计算机科学王冠上的明珠；考虑到我贫瘠的智商，以后估计不会朝 TCS 方向来走；但对这些优雅的理论有一个最基本的了解应当是 CS 学生的素养。

讽刺的是，你坑近二十年前就没有开设这门课了 [1]，只得留待交换来上。老师是印度人，口音很重，我听完整节课才明白他口中的「GEO」其实是「zero」。

完整的笔记和错题集归档在博客园，这里就留下一点比较精华的东西吧！

This article is a self-administered course note.

It will NOT cover any exam or assignment related content.

DFA & NFA

DFA (Deterministic Finite Automaton) 确定有限状态自动机：有向图，一个开始状态 (starting state)，若干个接受状态 (accepting state)。边上带 label 用来标示转移。每个状态出度为 1 (出度为 0 的状态默认向 dead state 转移)。

NFA (Non-deterministic Finite Automaton) 非确定有限状态自动机：DFA 但每个状态出度可以大于 1。并且它的不确定性允许空转移 $ϵ$ -transition，即不带 label 的边。

NFA 与 DFA 在 language recognition 意义上等价。

DFA 显然是出度为 1 的 NFA。
NFA 转 DFA 稍微麻烦点：因为 $| δ (q, α) | \geq 1$ ，我们直接令 $δ_{D} ({q}, α) = {δ (q, α)}$ ，把集合视为一个状态。重定义的转移 $δ_{D}$ 如下： $δ_{D} (Q, α) = {\cup_{q \in Q} δ (q, α)}$ 。这样，新 DFA 的状态数量要 exponentially more than 原 NFA。

什么是正则语言 (Regular Language) - 首先要知道什么是语言，语言就是满足某种规律的字符串集合 - 正则语言就是能被 DFA/NFA 识别的语言。

我们熟悉的正则表达式 (Regular Expression) 是一种可以描述正则语言规律的表达式，简单来说，就是用单个字符串 (表达式) 来表示字符串集合 (语言)。因此也可以这样说：正则语言是可以被正则表达式表示的语言。

符合直觉地，任意 DFA 可以转化为一个正则表达式；任意正则表达式可以转化为一个 $ϵ$ -NFA (具体 DP 方法见归档笔记)。

怎样把 DFA 化为最简形式 (minimization of DFA)，即，等价 DFA 中状态数最少的？

又是 DP。定义 $f_{i, j} = 1 / 0$ 为状态 $i$ 与状态 $j$ 是否 distinguishable。初始化：

$f_{s, t} = 1$ where $t \in T$ 。显然起始状态与接收状态是可被空串 $ϵ$ 分辨的。
$f_{i, j} = 0$ otherwise。

开始 DP，已知使用长度为 $x$ 的字符串时分辨情况为 $f$ ，推出使用长度为 $x + 1$ 时的字符串时的分辨情况 (为了节省空间，这里 $f$ 其实省略了长度维度 $x$ )。转移方程 $f_{p, q} = 1$ if $\exists α, f (δ (p, α), δ (q, α)) = 1$ 。不断增加长度直到 $f$ 收敛，我们就获得了所有的 indistinguishable pairs (被 $f$ 标记为 0)；在原 DFA 中合并每一对不可分辨状态对即可。

Pumping Lemma for RL

Pumping Lemma (泵引理) 将会伴随整个计算理论课程，在这里我将首先介绍其 RL 版本。

若 $L$ 是正则语言，那么存在某常数 $n$ 使得对于任意长度 $\geq n$ 的字符串 $w \in L$ ，我们都能找到一种方式将其分解为 $w = x y z$ ，并满足：

$y \neq ϵ$
$| x y | \leq n$
对所有整数 $k \geq 0$ ，字符串 $x y^{k} z \in L$

这里 $y^{k}$ 表示将子串 $y$ 重复 $k$ 次。

这应该是所有泵引理中最容易证明的一个了：考虑某个能够识别 $L$ 的 DFA，令 $n = | Q | + 1$ ( $| Q |$ 为该 DFA 的状态数)。对于长度 $\geq n$ 的某个 $w \in L$ ，根据鸽巢原理我们能够肯定至少存在一个状态 $q_{r e p}$ 被经过了两次。这意味着在转移过程中一定出现了某个环 ( $q_{r e p}$ 作为该环的扭结)。我们令 $y$ 等于这个环对应的字符串即可。

所有正则语言都满足泵引理，但也存在满足泵引理的非正则语言。因此泵引理常用来证否：若找到某个长度 $\geq n$ 的字符串，不存在任意一种 $x y z$ 的划分方式能使得对于所有 $k$ ， $x y^{k} z \in L$ ，那么 $L$ 不是正则的。

PDA

PDA (Push Down Automata) 下推自动机是一种外置一个无限长的数据栈的有限状态自动机。转移条件不仅与当前读入的字符有关，也与栈顶元素有关。

转移 $(q, γ) \in δ (p, a, X)$ 表示，当前状态为 $p$ ，栈顶元素为 $X$ ；此时读入字符 $a$ ；NPDA 能够 (DPDA 则是仅能) 转移至状态 $q$ ，且 $X$ 从栈中弹出， $γ$ 被压入栈中。

引入一种新的 notation，瞬时描述 (instantaneous description)。它是一个三元组 $(q, w, a)$ 表示当前状态为 $q$ ，剩余需要读入的字符串为 $w$ ，当前栈顶元素为 $a$ 。使用 $⊢$ (单步) 或 $⊢^{*}$ 进行转移。

上下文无关语言 (Context-Free Language) 是能够被 PDA 识别的语言。任意 CFL 都能被上下文无关语法 (Context-Free Grammar) 表达，或者，更准确地说，生成。

PDA - CFL - CFG 的关系与 DFA - RL - RE 的关系近似。

同样的，对任意 CFG 都能构造一个等价的空栈 PDA 来识别，对任意 PDA 都能构造一个等价的 CFG 生成相同的语言。证明见归档笔记，利用了 NPDA 的非确定性。

CFG $G$ 由四部分构成， $V$ (变量，variables)， $T$ (终止符，terminals)， $S$ (起始符，start symbol) 与 $P$ (生成规则，production rules， $\to$ )。

$G$ 所生成的 CFL $L (G) = {w \in T^{*} | S \Rightarrow^{*} w}$ 。从起始符开始，根据若干生成规则不断转移 (引入变量，消去变量，引入终止符)，直至生成最终的字符串 (全由终止符构成，无法再生成)，这一过程被称为派生 (derivation)。显然，派生过程可以用一颗树来描述，该树被称为 CFG 的分析树 (parse tree)，或具体语法树 (concrete syntax tree)。

若同一个字符串存在两种派生方式 (存在两种形态有异的分析树)，我们说该语法是歧义的 (ambiguous)。

Chomsky Normal Form

乔姆斯基范式 (Chomsky Normal Form) 是一种特殊的 CFG 范式，它规定该 CFG 的分析树是一颗二叉树。从生成规则上看，乔姆斯基范式要求每一种生成规则都满足以下形式：

$A \to B C$ ( $A, B, C$ 均为变量 $\in V$ )
$A \to α$ ( $A$ 为变量 $\in V$ ， $α$ 为终止符 $\in T$ )

任意 CFG 都能转化为乔姆斯基范式。

第一步：消除所有空生成 ( $ϵ$ productions)，即 $A \to ϵ$ 这样的规则。

去掉所有的 $A \to ϵ$ 规则，并把 $A$ 标记为空变量 (nullable variables)。
检查其他的规则，若规则 $B \to s$ 中， $s$ 包含空变量，则排列的 (permutation) 删去这些空变量。举个例子 $S \to A S A$ ，删去后产生四个新规则 $S \to A S A | S A | A S | S$ 。

第二步：消除所有单元生成 (unit productions)，即 $A \to B$ ， $A, B$ 均为变量这样的规则。直接去掉所有的 $A \to B$ 规则，如果有 $B \to s$ ，则添加 $A \to s$ 。

经以上两步， $G$ 中所有的生成规则 $A \to s$ 都表现成以下两种形式：

$| s | = 1$ ，此时 $s$ 一定是单个终止符。
$| s | = | s_{1} s_{2} . . . s_{n} | = n \geq 2$ ， $s_{i}$ 是终止符或者变量。

第三步：把所有生成规则转化为 $A \to B C$ 或 $A \to α$ 的形式。举例来说，给定 $A \to s_{1} s_{2} . . . s_{n}$ ，我们从 $i = 1$ 开始逐个进行拆解：

若 $s_{1}$ 是变量， $A \to s_{1} B_{2}$
若 $s_{2}$ 是变量， $B_{2} \to s_{2} B_{3}$
以此类推，若 $s_{i}$ 是变量， $B_{i} \to s_{i} B_{i + 1}$
若某个 $s_{i}$ 是终止符，令 $B_{i} \to Z_{i} B_{i + 1}$ ，其中 $Z_{i} \to s_{i}$

Pumping Lemma for CFL

来了！关于上下文无关语言 CFL 的泵引理。

若 $L$ 是上下文无关语言，那么存在某常数 $n$ 使得对于任意长度 $\geq n$ 的字符串 $z \in L$ ，我们都能找到一种方式将其分解为 $z = u v w x y$ ，并满足：

$| v w x | \leq n$
$v x \neq ϵ$
对所有整数 $k \geq 0$ ，字符串 $u v^{k} w x^{k} y \in L$

这一泵引理证明起来就有点复杂了。给定 CFG $G = (V, T, P, S)$ 且 $L (G) = L$ 。令 $m = | V |$ (变量数)， $n = 2^{m}$ 。

考虑一个长度 $> n = 2^{m}$ 的字符串 $z \in L$ ，它的分析树中一定至少存在一条从根到叶的路径，其长度 $\geq m + 1$ (即使分析树是完全二叉树，此时深度最小，为 $m + 1$ )。

考虑这一路径上的后 $m + 1$ 个变量 (从底部往上数)，根据鸽巢原理，其中至少存在一对同样的变量，记为 $A$ 。

repetition: A\Rightarrow^* A — repetition: $A \Rightarrow^{*} A$

见上图，我们按照这种方式进行分割 $S \Rightarrow_{G}^{*} u A y \Rightarrow_{G}^{*} u v A x y \Rightarrow_{G}^{*} u v w x y$ 。

条件一： $A$ 是 $S$ 的深为 $m + 1$ 的子树，其叶子数量 ( $| v w x |$ ) 不会超过 $2^{m} = n$
条件二： $A$ 子树非空，一定能保证 $v x \neq ϵ$
条件三：既然有 $A \Rightarrow_{G}^{*} v A x$ 且 $A \Rightarrow_{G}^{*} w$ ，先不断使用式一 $A \Rightarrow_{G}^{*} v^{k} A x^{k}$ ，再使用式二 $v^{k} A x^{k} \Rightarrow_{G}^{*} v^{k} w x^{k}$ 。于是有 $S \Rightarrow_{G}^{*} u A y \Rightarrow_{G}^{*} u v^{k} w x^{k} y$ ；既然该字符串能被 $G$ 产生，它同样属于原 CFL $L$ 。

Turing Machine

来到最强大的通用计算模型图灵机 (Turing Machine) 了。

无限长的纸带 (tape)，读写头 (read-write head) 在该纸带上进行转移。转移方程如下： $δ (p, α) = (q, β, L / R)$ 。意义为：图灵机在状态 $p$ ，当前读到的字符为 $α$ ；那么图灵机转移到状态 $q$ ，读写头将当前单元的字符 $α$ 更改为 $β$ ，读写头向左/右移动一个单元。

读写头若到达任意接受状态 (accepting state)，纸带上的字符串被视为接受。与 DFA/PDA 不同，图灵机不要求访问纸带上的所有字符 (前两个自动机均要求 consume 输入字符串的所有字符)。这一特性决定了图灵机可能在转移过程中陷入死循环，即，不停机 (halt)。

图灵机的瞬时描述 (instantaneous description)： $x_{0} x_{1} . . . x_{n - 1} q x_{n} . . . x_{m}$ 。实际上就是把图灵机的状态 $q$ 插入纸带的内容 $x_{0} x_{1} . . . x_{m}$ 里！其实挺形象的。

图灵机存在许多变种：半无限带式图灵机 (semi-infinite tape TM)，多带图灵机 (multi-tape TM)，非确定性图灵机 (nondeterministic TM)；但它们在语言识别意义上均与单带确定性图灵机等价 (区别在于时空复杂度)。

通用图灵机 (Universal TM) 是能够识别通用语言 (Universal Language) $L_{u} = {(M, w) : M accepts w}$ 的图灵机。输入模式为 $M # w$ 。

这里要涉及一个概念，图灵机的编码 (coding scheme)。简单理解就是把图灵机编码成一个字符串；我们甚至可以通过遍历所有字符串来列举所有图灵机。

通用图灵机所做的只是 simulate $M (w)$ ，若 $M$ 接受 $w$ ，通用图灵机也接受。

Decidability

几个概念。

递归可枚举语言 (Recursively Enumerable Language) 是能被图灵机识别的语言。
递归语言 (Recursive Language)，或可判定语言 (Decidable Language)，是能被图灵机识别，且在所有输入上都能停机的语言。
部分递归函数 (Partial Recursive Function) $f$ — 很明显 TM 是一个函数，输入是 TM 处理前的纸带，输出是 TM 处理后的纸带 — 是能被图灵机计算，且该图灵机在 $f$ 的定义域上停机，在 $f$ 的定义域外不停机的函数。
递归函数 (Recursive Function) $f$ — 是能被图灵机计算，且该图灵机在所有输入上都停机的函数。

显然，比起递归可枚举，递归是一个更强的约束。

一些有趣的结论：对角语言 (Diagonal Language) $L_{d} = {w_{i} : w_{i} \notin L (M_{i})}$ (注意，字符串可以被列举，图灵机的编码也可以被列举) 是 non-RE 语言。通用语言的补 $\overset{―}{L_{u}} = {(M, w) : M doesn't accept w}$ 也是 non-RE 语言。非空图灵机语言 $L_{n e} = {M : L (M) \neq \emptyset}$ 是 RE 语言，但空图灵机语言 $L_{e} = {M : L (M) = \emptyset}$ 是 non-RE 语言：这意味着我们无法判断一个给定的图灵机是否为空 (empty language problem)。

规约 (Reduction)： $P_{1}$ 规约为 $P_{2}$ (表记 $P_{1} \leq_{m} P_{2}$ ) 若存在某个递归函数 $f$ 满足 $x \in P_{1}$ 当且仅当 $f (x) \in P_{2}$ 。规约关系说明了：

如果 $P_{2}$ 是递归的， $P_{1}$ 也是递归的
如果 $P_{2}$ 是递归可枚举的， $P_{1}$ 也是
如果 $P_{1}$ 是不可判定的， $P_{2}$ 也是
如果 $P_{1}$ 不是递归可枚举的 (non-RE)， $P_{2}$ 也不是

一开始我是把这个规约按照 COMP3357 中的那个规约理解的，后来发现两者不太一样。见后文关于 Karp Reduction 与 Cook Reduction 的讨论。

莱斯定理 (Rice's Theorem)：递归可枚举语言的所有非平凡性质 (non-trivial property) 都是不可判定的。

非平凡性质 $p$ ：至少有一个 RE 语言满足 $p$ ，也至少存在一个 RE 语言不满足 $p$ 。
$L_{p} = {M | L (M) satisfies property P}$ 是不可判定的。

莱斯定理的详细证明见归档笔记，比较巧妙，可以将这个问题归约到空语言问题 (empty language problem) 上。

我们知道通用语言是递归可枚举的，但是它是可判定的吗？另一个在课上提到的例子是将波斯特对应问题 (Post's Correspondence Problem) 归约到通用语言。PCP 是著名的不可判定问题，因此我们能够确定通用语言递归可枚举，但不可判定。这个例子的证明也很巧妙，可见归档笔记，感觉我长了五个脑子也想不出来。

Halting Problem

著名的停机问题，这个必须得记录一下。

INSTANCE：下标 $i, j$
PROBLEM：第 $i$ 个图灵机 $M_{i}$ 是否在输入第 $j$ 个字符串 $w_{j}$ 后停机？

反证法。假设停机问题是可判定的，那么一定存在某个图灵机 $H$ 接受 $L = {(i, j) : M_{i} halts on w_{j}}$ 且在所有输入上停机。

构造一个悖论图灵机 (Paradoxical Turing Machine) $D$ ，输入某个下标 $k$ ，模拟 $H (k, k)$ ：

若 $H$ 接受 $(k, k)$ ，即， $M_{k}$ 在 $w_{k}$ 上停机，则令 $D$ 陷入死循环 (不停机)
若 $H$ 拒绝 $(k, k)$ ，即， $M_{k}$ 在 $w_{k}$ 上不停机，则令 $D$ 停机

$D$ 本身也是图灵机，这说明它可以被编码并且有对应的下标 $d$ 。现在我们分析一下 $D (d)$ 的表现：

若 $D$ 不在 $w_{d}$ 上停机，说明 $H$ 接受 $(d, d)$ ，即 $M_{d} \Rightarrow D$ 在 $w_{d}$ 上停机！悖论产生
若 $D$ 在 $w_{d}$ 上停机，说明 $H$ 拒绝 $(d, d)$ ，即 $M_{d} \Rightarrow D$ 不在 $w_{d}$ 上停机！悖论产生

推出矛盾。假设为假：因此停机问题是不可判定问题。

P & NP

来正式认识一下 P 与 NP 问题。

P 问题：所有能够被一个确定性图灵机 (Deterministic TM) 在多项式时间内求解的问题。

NP 问题：所有能够被一个非确定性图灵机 (Nondeterministic TM) 在多项式时间内求解的问题。

显然有 $P \subseteq N P$ 。P 问题代表的是一种可解性 (任何经典意义上的多项式算法都能被视作一个确定性图灵机)，那么 NP 问题代表的是什么呢？

命题：若 $L \in N P$ ，存在一个确定性多项式时间的可计算谓词 (computable predicate) $P (x, y)$ ，与一个多项式 $q (\cdot)$ ，满足： $\begin{matrix} (1) & x \in L ⟺ \exists y : | y | \leq q (| x |) such that P (x, y) = 1 \end{matrix}$ 证明很符合直觉。我们知道 NTM 的转移是不确定的，即， $| δ (q, α) | \geq 0$ 。作为理论模型的 NTM 能够平行探索 (parallel exploration) 所有可能性，但这样的神力并不 physically 存在。因此，一个真正可计算的方案是用 $y$ 消除 NTM 的非确定性，即， $y$ 标志着 NTM 下一步选择哪一个可能性进行转移，类似于导航：如果 NTM 接受了 $x$ ，令 $P (x, y) = 1$ ，否则 $P (x, y) = 0$ 。因为 NTM 能在多项式时间内接受 $x$ ，显然 $y$ 的长度也是多项式级别的。

我们把这样的 $y$ 称为 $x$ 的证明 (proof, or certificate)。虽然我们无法在多项式时间内判定 $x \in L$ (NTM 不存在)，但可以在多项式时间内验证 (verify) 给定的 $y$ 是否能使得 $P (x, y) = 1$ 。

因此，有人说 NP 问题代表的是一种可验证性 (verifiable)。找出解的过程也许是困难的，但验证解的过程是简单的。这也是 $P \neq N P$ 的一个重要理论基础：我们真的能够相信，验证一个问题的解与找出一个问题的解有着相同的难度吗？

或者说，「真理的存在」一定代表着「真理是可被认识」的吗？

NPC

定义 Karp 规约 (Karp Reduction) $L_{1} \leq_{m}^{p} L_{2}$ ：存在多项式时间可计算的函数 $f$ ，满足 $x \in L_{1} ⟺ f (x) \in L_{2}$ 。因此有时 Karp 规约也被称为多项式时间规约 (Poly-Time Reduction)。

我们在加密学 COMP3357 中接触到的规约是 Cook 规约 (Cook Reduction)；其特征是所调用的预言机 (Oracle) 是一个确定性多项式时间的机器，且可以被调用任意次数。而在本节课中提到的 Karp 规约仅能调用预言机一次。

NP 困难问题 (NP Hard) $L_{h a r d}$ 满足： $\forall L^{'} \in N P . L^{'} \leq_{m}^{p} L_{h a r d}$ 。

NP 完全问题 (NP Complete) $L_{c o m p}$ 满足：

$L_{c o m p} \in N P$
$L_{c o m p} \in N P Hard$ ，即 $\forall L^{'} \in N P, L^{'} \leq_{m}^{p} L_{c o m p}$

注意，NP hard 问题不一定是 NP 问题 (它可以比 NP 问题更困难，即，其答案都是难以验证的)，但 NP complete 问题一定是 NP 问题。

由于所有的 NP 问题都能归约到 NPC 问题，若任意一个 NPC 问题在多项式时间上可解 ( $\exists L \in N P C, L \in P$ )，整个 NP 问题集都将在多项式时间上可解 ( $P = N P$ )。

著名的 NPC 问题：

可满足性问题 Satisfiability，e.g., 3-SAT
三维匹配问题 3D Matching
顶点覆盖问题 Vertex Cover (一个顶点覆盖所有邻接的顶点)
最大割问题 MAX-CUT
K-问题 K-Clique (图中是否存在一个规模为 $k$ 的团/完全子图)
独立集问题 Independent Set (独立集中任意两个顶点都不相连)
哈密顿回路问题 Hamiltonian Circuit (每个顶点会且仅会被访问一次)
划分问题 Partition (正整数集合的等和分割)
集合覆盖问题 Set Cover
旅行商问题 Traveling Salesman Problem, TSP (权重和 $\leq B$ 的哈密顿回路)

3-SAT 归约到顶点覆盖问题。有 $n$ 个变量， $m$ 个 3-SAT clauses，构造出一个点数为 $2 n + 3 m$ 的图，分别是 $n$ 个 $x_{i}$ ， $n$ 个 $\neg x_{i}$ ， $m$ 个三角形，每个三角形对应一个 clause 中的三个 literals。连边策略很显然：该图的顶点覆盖对应的是原 3-SAT 的一个解。

三个图论 NPC 问题 (Vertex Cover, Independent Set, K-Clique) 的规约关系：如果图 $G = (V, E)$ 有一个规模为 $k$ 的顶点覆盖，那么它有一个规模为 $| V | - k$ 的独立集，且 $\overset{―}{G} = (V, E^{c})$ 有一个大小为 $| V | - k$ 的完全子图。

Reference

This article is a self-administered course note.

References in the article are from corresponding course materials if not specified.

Course info: CS3231. Professor: Sanjay Jain.

Course textbook: Introduction to Automata Theory, Languages and Computation (3rd Edition), Hopcraft, Motwani & Ullman, (2014), Pearson

Course website: https://www.comp.nus.edu.sg/~sanjay/cs3231.html

[1] 引自杨老师，摘录如下：「据考证，本科生课程 CSIS0293/COMP3293 Introduction to Theory of Computation 最后一次开设是在 Autumn 2005，研究生课程 CSIS9601/COMP9601 Theory of Computation and Algorithm Design 最后一次开设是在 Autumn 2016。」

-----------------------------------そして、次の曲が始まるのです。-----------------------------------