Lecture 9. The Class NP NP 类
非确定性复杂度
定义：如果一个非确定性图灵机，对于任意长度为 $n$ 的输入，所有的分支都会在 $t(n)$ 步骤内停机，那么这个非确定性图灵机（NTM）就是 $t(n)$ 时间的。简而言之，所有的分支对所有的输入停机。
定义：$\operatorname{NTIME}(t(n)) = \{B \mid \text{存在 } O(t(n)) \text{ 时间的单带非确定性图灵机能够判定 } B\}$。
定义：$NP = \bigcup_k \operatorname{NTIME}(n^k)$，也就是所有的非确定性单带图灵机在多项式时间内能够判定的 语言 的集合。
对于合理的非确定性计算模型，$NP$ 是不变的。
NP 问题举例
哈密顿路径问题（NP）
$M =$ "对于输入 $\langle G, s ,t \rangle$：
- 设图中一共有 $n$ 个节点
- 非确定性的写下一个长度为 $n$ 的数列，$v_1, v_2, \cdots, v_n$，代表 $n$ 个节点
- 如果 $v_1 = s$，$v_n = t$，$v_i$ 互不相等，且 $\forall i \in [1, n-1], (v_i, v_{i+1}) \text{ 是图中一条边}$，就接受
- 任意一个检查条件不满足，这个分支就拒绝"
思考：$\overline{HAMPATH} \in NP$ 吗？答案是：不知道。有人认为，之前拒绝的操作换成接受，接受的操作换成拒绝，就可以了，其实不行。因为简单的把非确定性机器的响应翻转，并不能识别原问题的补。
合数问题（NP，也 P）
$COMPOSITES = \{x \mid x \text{ 是合数}\}$。下面证明 $COMPOSITES \in NP$。
$M =$" 对于输入 $x$，
- 非确定性的选一个 $(1, x)$ 当中的一个整数 $y$
- 若 $x \bmod y = 0$ 则接受，否则这个分支拒绝"
事实上，有数学家证明过，$COMPOSITES \in P$ 也是同时成立的。
NP 与 P 的关系
- NP：成员资格可以多项式时间内验证（verify）的语言类。比如对于哈密顿路径的存在性问题，我只要随便给出一条哈密顿路就可以；对于是不是合数的问题，我只要随便给出一个因子就可以。
- P：成员资格可以多项式时间内判定（determine）的语言类。要求更高一点。
通常认为 $P \subseteq NP$。
- $P = NP$？不知道。有的同时属于 $P$ 和 $NP$ 了，但所有问题都既 $NP$ 又 $P$ 吗？
- $P \not= NP$？不知道。因为 $P$ 太强大了，可能有一个问题暂时没有找到 $P$ 的解法，只是因为人脑比较笨。相当于可能有一个爆搜算法，明明可以优化，可是人类太笨了，想不出来怎么优化。
回忆一下 NFA 转 DFA，状态数变成了 $2^n$ 个，也就是变成了指数级别。所以现在已知的是，$NP \subseteq EXPTIME = \bigcup_k \operatorname{TIME}(2^{n^k})$。
验证机 verifier
定义：语言 $A$ 的 验证机（verifier） 是一个算法 $V$,这里 $A = \{w \mid \text{对于某个额外字符串 } c \text{，} V \text{ 接受 } \langle w, c \rangle\}$。这里的 $c$ 是一个额外的信息，称为 证书（certificate）。验证机通过 $c$ 来验证输入的字符串 $w$ 是否是 $A$ 的成员。对于上面哈密顿路和合数问题，证书分别是随便一条哈密顿路和随便一个因子。
多项式时间验证机（polynomial time verifier），在 $|w|$ 的多项式时间内运行。若语言 $A$ 拥有一个多项式时间验证机，那么这个语言就是 多项式可验证的（polynomially verifiable）。对于多项式验证机，证书具有 $|w|$ 的多项式长度。
有定理表明：$NP$ 是具有多项式时间验证机的语言类。
还有定理表明：一个语言是 NP 的，当且仅当他能被某个非确定性多项式时间图灵机判定。
既 NP 又 P 问题举例
1. $A_\text{CFG} \in NP$
之前已经证明过 $A_\text{CFG}$ 是可判定的。转化为乔姆斯基范式之后，可以证明它是 $NP$ 的。大致思路是，对于输入 $\langle G, w \rangle$，把 $G$ 转换成乔姆斯基范式，非确定性的选择（随便猜）一个长度为 $2|w|-1$ 的派生过程，看看这个派生过程能否派生出串串 $w$。（回忆一下，之前证明这个语言可判定是枚举了所有的派生过程）。因此，$A_\text{CFG} \in NP$。
2. $A_\text{CFG} \in P$
想不到竟然还是 $P$ 吧？证明在中文课本 183 页。
最初先设计了一个普通递归（爆搜），但是时间复杂度不对，于是再改成记忆化搜索（动态规划）。
$D =$ "对于输入 $\langle G, w \rangle$，
- 如果之前已经算出了对于 $\langle G, w, R \rangle$ 的值，就直接返回
- 对于每个 $w_i$ 和每一个变元 $R$，检查是否存在替换规则 $R \rightarrow w_i$，把结果存储到 $\langle G, w_i, R \rangle$ 里。相当于代码实现的 dp 数组初始化。
- 从 $len \in [2, n]$ 依次枚举子串的长度（$O(n)$）
- 然后枚举左端点 $i \in 1, n - len + 1$，设右端点 $j = i + len - 1$，得到所有长度为 $len$ 的子串。（$O(n)$）
- 从 $k \in [i, j - 1]$ 枚举断点 $k$ 把当前字串 $u$ 分割成 $u = xy$（$O(n)$）
- 对于每一个替换规则 $R \rightarrow ST$，若 $\langle G, x, S \rangle$ 和 $\langle G, y, T \rangle$ 都真，则把 $\langle G, u, R \rangle$ 设为真。这一步的时间复杂度仅与 CFG 的规则数有关，是常数。
- 从 $k \in [i, j - 1]$ 枚举断点 $k$ 把当前字串 $u$ 分割成 $u = xy$（$O(n)$）
- 然后枚举左端点 $i \in 1, n - len + 1$，设右端点 $j = i + len - 1$，得到所有长度为 $len$ 的子串。（$O(n)$）
- 最终，设 $S$ 是起始变元，检查 $\langle G, w, S \rangle$ 是否为真。如果是，则接受。否则拒绝。"
这个算法的时间复杂度是 $O(n^3)$ 的。所以 $A_\text{CFG} \in P$。
由于 CFG 和 CFL 等价，所以如果 $A_\text{CFG} \in P$，也能推出 $A_\text{CFL} \in P$。
多项式可归约性
可满足性问题（SAT）satisfiability problem
布尔代数的三种符号：$\wedge$（与），$\vee$（或），$\neg$（非）。
定义：对于布尔表达式 $\phi$，如果可以分配给每个变量一个值使得 $\phi = \text{true}$，则称这个 $\phi$ 是 可满足（satisfiable） 的。
定义语言 $SAT = \{ \langle \phi \rangle \mid \phi \text{ 是一个可满足的布尔表达式}\}$。显然，$SAT \in NP$。因为可以找到一个证书（一组赋值），然后在多项式时间内验证（直接求值）。之后将证明 $SAT$ 还是 NP 完全的。
曾有科学家指出，若 $SAT \in P$，则可推出 $P = NP$。因为所有的 NP 问题都可以多项式时间归约到 $SAT$，就像所有的图灵可识别语言都可以映射规约到 $A_\text{TM}$ 一样。所以一旦证明了 $SAT \in P$，就可以利用归约的性质，推出 $P = NP$。然而到目前为止，既不知道 $SAT \in P$ 还是 $SAT \not\in P$。更确切的说，$SAT \in P$ 当且仅当 $P = NP$。
多项式可归约性
定义：若 $A \leq_m B$，且这个可计算归约函数可以在多项式时间内完成计算，那么 $A$ 就是 多项式可归约（polynomial time reducible） 到 $B$ 的，记作 $A \leq_p B$。
定理：若 $A \leq_p B$ 且 $B \in P$ 则可推出 $A \in P$。如图，$f$ 是多项式时间内可计算的函数：
