Lecture 10. NP Complete NP 完全

EXPTIME 指数时间类

exp 是 exponential 的意思。

定义：$EXPTIME = \bigcup_k \operatorname{TIME}(2^{n^k})$，即所有在指数时间内可判定的语言的集合（集合的集合）。

故：$NP \subseteq EXPTIME$。但是我们不知道 $NP$ 是否是更小的确定性时间复杂度类的子集。（怎么听起来有点像连续统假设呢？）

3-SAT 问题与 CLIQUE 问题

首先定义 合取范式（Conjunctive Normal Form，CNF）：具有 $\phi=\underbrace{(x \vee \bar{y} \vee z)}_{\text {clause }} \wedge \underbrace{(\bar{x} \vee \bar{s} \vee z \vee u)}_{\text {clause }} \wedge \cdots \wedge(\bar{z} \vee \bar{u})$ 形式的布尔表达式。其中每个括号包起来（子句，clause）的都用 $\vee$ 连接，括号与括号之间用 $\wedge$ 连接。相当于数电当中学的 POS 形式。如果 CNF 是可满足的，那就意味着每一个子句当中，都至少有一个变量能取到真。

另外，定义 3CNF 表示每个从句都恰好含有 3 个变量。

最后定义：$3SAT = \{\langle \phi \rangle \mid \phi \text{ 是一个可满足的 3CNF}\}$。

此外还有一个 团（clique） 的概念：k-clique 指的是一个图当中大小为 $k$ 的完全连通子图。

$CLIQUE = \{\langle G, k \rangle \mid \text{无向图 } G \text{ 具有一个 }k \text{-clique}\}$。

定理：$3SAT$ 多项式时间可归约到 $CLIQUE$，即 $3SAT \leq_p CLIQUE$。因为 $\phi$ 是可满足的，当且仅当图 $G$ 拥有一个 $k$-clique。其中 $k$ 是子句的数量。证明可以考虑分别从两个方向进行：

充分性（$\rightarrow$）：若 $\phi$ 可满足，意味着 $\phi$ 的 $k$ 个子句当中都至少有一个变量取真。那么把这 $k$ 个变量抽出来，就可以形成一个 $k$-clique。

必要性（$\leftarrow$）：假如存在一个 $k$-clique，由于每个子句当中的三个节点都互不连通，所以团当中的任意两点都不在同一个子句，所以团里的 $k$ 个节点恰好来自 $k$ 个不同的子句。直接把这 $k$ 个变量赋值真（由于 $a$ 与 $\neg a$ 之间没有连边，所以这样赋值不会产生 $a$ 与 $\neg a$ 同时真的情况），这样这个 $\phi$ 就可满足了。

这个证明完全没有用到 $3$ 的性质，所以对于任意的 $k-SAT$ 问题，都可以多项式时间可归约到 $CLIQUE$。

推论：$CLIQUE \in P \rightarrow 3SAT \in P$。

NP-完全

定义：若语言 $B \in NP$ 且 $\forall A \in NP, A \leq_p B$ 则称 $B$ 是 NP-完全 的。

也就是说，NP-完全类，像是一个标杆。

要证明某个问题是 NP-完全的，可以先证明这个问题是 NP 的，再找一个已知的 NP-完全问题，证明两个问题之间多项式时间可归约。

NP 完全类对于证明 $P \not= NP$ 有重要作用。

常见 NP 完全问题

SAT 问题（库克-列文定理）
3-SAT 问题
CLIQUE 问题
VERTEX-COVER 问题（顶点覆盖问题）
HAMPATH 问题（哈密顿路径问题）
UHAMPATH 问题（无向图的哈密顿路径问题）
SUBSET-SUM 问题（子集和问题）

HAMPATH 问题的 NP 完全性证明

核心是证明 3-SAT 多项式可归约到 HAMPATH。

没学明白。考试不考。

UHAMPATH 问题的 NP 完全性证明

先证明 NP 性：非确定性的选择一条路径，然后检查是否恰好包含所有节点各一次即可。

然后证明