🧠3-SAT、CLIQUE与“P=NP?”
计算机理论中一个绕不开的话题是 P 与 NP 是否相等的问题，它也是尚未解决的千禧年大奖难题之一。这个问题在 1970 年代由 Stephen A. Cook、Leonid Levin 等人的工作奠定了现代复杂度理论的基础。
本文通过两个经典的 NP-complete 问题——3-SAT 与 CLIQUE——来直观理解 P、NP、NP-complete，以及“问题之间的多项式时间归约”到底意味着什么。
1. P、NP 与 NP-complete
1.1 P
P（Polynomial Time） 严格来说是可以由确定性算法在多项式时间内判定的语言（或等价地，判定问题）的集合。
常见的多项式时间复杂度包括：
例如，给定一个无序数组和阈值 T，判断“是否存在元素不小于 T”可以在线性时间内完成，因此这个判定问题属于 P。
1.2 NP
NP 并不是 “non-polynomial”，而是 Nondeterministic Polynomial Time。
一个常用的理解方式是：
如果对每个“是”实例都存在一个长度至多为输入规模多项式的证书，并且给定证书后可以在多项式时间内验证，那么这个判定问题属于 NP。
因此：
因为一个能够在多项式时间内直接求解的问题，当然也可以在多项式时间内验证它的解。
1.3 NP-complete
NP-complete（NP 完全） 问题需要同时满足两个条件：
- 它属于 NP；
- 所有 NP 问题都可以在多项式时间内归约到它，也就是它是 NP-hard 的。
需要特别注意：NP-complete 的定义并不要求它已知“不属于 P”。如果未来有人证明某一个 NP-complete 问题存在多项式时间算法，那么将立即得到：
这些关系更安全地概括为：
注意：由于目前并不知道 P 是否等于 NP，不能把 NP-complete 直接画成“确定落在 NP 内但 P 外”的区域；若任何一个 NP-complete 问题属于 P，就会推出 P = NP。
因此，P 与 NP 是否相等的核心问题可以理解为：
NP 中那些最难的 NP-complete 问题，究竟能不能也在多项式时间内求解？
至今仍没有答案。
2. 3-SAT problem
来看一个经典的 NP-complete 问题：3-SAT。
给定一组布尔变量：
把它们组成合取范式（CNF）：
其中每一个子句 C_i 恰好包含三个文字（literal），每个文字可以是某个变量，也可以是它的否定。例如：
所谓 3-SAT 问题，就是问：
是否存在一组 X_1,X_2,...,X_n 的真假取值，使整个布尔表达式为真？
3-SAT 属于 NP：给定一组候选赋值后，对每个子句检查三个文字即可；若有 m 个子句，验证工作量与 m 成线性关系，因此是多项式时间。
但是，要直接寻找一组满足公式的赋值，最朴素的方法是枚举全部：
种可能的布尔赋值。
3-SAT 已被证明是 NP-complete。它的意义不只是“目前没有发现快速算法”，而是：任何 NP 问题都能在多项式时间内转化为 3-SAT。
这引出了复杂度理论中极重要的思想——归约（reduction）。
3. CLIQUE problem
先回顾完全图。
如果一个无向图中任意两个不同顶点之间都有边，那么它就是完全图。常用 K_n 表示包含 n 个顶点的完全图：
3.1 Clique（团）
对于无向图：
如果一个顶点子集 S 中任意两个不同顶点之间都有边，那么 S 就构成一个 clique（团）。
例如下面这个图：
可以找到两个大小为 3 的 clique：
CLIQUE 判定问题的标准形式是：
给定无向图 G=(V,E) 和整数 k，判断 G 中是否存在一个至少包含 k 个顶点的 clique。
CLIQUE 属于 NP：如果有人直接给出一个包含 k 个顶点的候选集合，只需要检查任意两点之间是否存在边，就能在多项式时间内验证它是否真的是一个 clique。
CLIQUE 同样是 NP-complete。
4. 从 3-SAT 归约到 CLIQUE
下面用一个具体例子看看如何把 3-SAT 转化成 CLIQUE。
考虑 3-SAT 公式：
记三个子句分别为 C_1,C_2,C_3。
4.1 为每个文字建立顶点
每个子句包含 3 个文字。我们给每个“文字在子句中的出现”建立一个顶点，因此这里一共有：
个顶点。
然后只在不同子句的顶点之间考虑连边。
连边规则是：
如果来自两个不同子句的两个文字不互相矛盾，就连接一条边。
例如 X_2 和它的否定不能同时为真，因此这两个顶点之间不连边；而 X_2 与 X_1、X_3 等不冲突，则可以连边。
以第三个子句中的 X_2 为例：
对所有顶点执行相同操作，得到完整归约图：
4.2 为什么要寻找大小为 m 的 clique？
原公式有 m 个子句。要证明这个归约正确，需要证明两个方向。
(⇒) 公式可满足，则图中存在 m-clique。
如果原公式有一个满足赋值，那么每个子句至少有一个为真的文字。从每个子句任选一个为真的文字，并取对应顶点。因为这些顶点来自不同子句，而且同一个真假赋值下不可能同时选到互为否定的一对文字，所以任意两点之间都有边；这 m 个顶点构成一个 clique。
(⇐) 图中存在 m-clique，则公式可满足。
如果构造图中有一个大小为 m 的 clique，那么：
- clique 中不可能选到同一个子句的两个顶点，因为同一子句内部没有连边；
- 因为 clique 有 m 个顶点，而一共只有 m 个子句，所以它必然恰好从每一个子句中选一个顶点；
- clique 中任意两个顶点之间都有边，因此这些被选中的文字彼此不矛盾；
- 因而可以构造出一组一致的布尔赋值，使每个子句至少有一个文字为真。
对于本例：
所以我们寻找一个大小为 3 的 clique。
例如下图红色三角形：
它选中了：
因此可以取：
这里 X_4 的值实际上可以任意选择，因为三个子句已经分别被 X_2、¬X_1、X_2 或 X_3 保证为真。
所以：
构造图共有 3m 个顶点，只需检查不同子句之间的顶点对，因此边数与构造时间均为 O(m²) 量级。于是这个转换本身是多项式时间的，我们完成了归约：
5. 归约意味着什么？
这类归约真正重要的地方在于：
如果我们有一个能够高效解决 CLIQUE 的算法，那么通过上述转换，也能高效解决 3-SAT。
更一般地说，NP-complete 问题之间可以通过多项式时间归约相互联系。于是，只要任何一个 NP-complete 问题被发现存在多项式时间算法，就会推出所有 NP 问题都存在多项式时间算法，即：
反过来，如果能够证明某一个 NP-complete 问题不可能存在多项式时间算法，那么也就证明了：
这也是为什么 3-SAT、CLIQUE、旅行商判定问题等经典 NP-complete 问题会在理论计算机科学中占据如此重要的位置。
Loading...