九、NP 完全性理论与近似算法

9.1 NP 理论基础

计算复杂性理论研究问题的计算难度，以及不同问题之间的难度比较。NP理论是其中最为核心的部分，为我们提供了衡量问题难解性的框架。

9.1.1 P、NP、NPC、NP-Hard 概念

决策问题

在研究计算复杂性时，我们通常关注决策问题，即只需要回答"是"或"否"的问题。任何优化问题都可以转化为对应的决策问题。例如，"找出图中的最短路径"可以转化为"图中是否存在长度不超过k的路径"。

P类问题

P类（Polynomial Time）是指可以在多项式时间内解决的决策问题集合。

• 形式定义：一个决策问题L属于P类，当且仅当存在一个确定性图灵机，它能在$O(n^k)$时间内解决L的任意实例，其中n是输入大小，k是常数。
• 例子：排序、最短路径、最小生成树、线性规划等。
• 特点：这些问题被认为是"易解的"，有高效算法。

NP类问题

NP类（Nondeterministic Polynomial Time）是指可以在多项式时间内验证解的正确性的决策问题集合。

• 形式定义：一个决策问题L属于NP类，当且仅当对于每个"是"实例，存在一个多项式长度的"证书"，使得确定性图灵机能在多项式时间内验证该证书的正确性。
• 例子：图着色、汉密尔顿回路、子集和等。
• 特点：尚未找到多项式时间的解法，但如果给出一个解，可以快速验证其正确性。

NP-Hard类问题

NP-Hard类（NP难问题）是指至少与NP中最难的问题一样难的问题。换句话说，所有NP问题都可以在多项式时间内规约到这些问题。

• 形式定义：如果对于任意$L^{\prime }\in NP$，存在从$L^{\prime }$到$L$的多项式时间规约，则问题$L$是NP-Hard的。
• 特点：NP-Hard问题不一定属于NP类，它们可能是决策问题，也可能是非决策问题。
• 例子：旅行商问题、集合覆盖问题。

NP-Complete类问题

NP-Complete类（NP完全问题）是既属于NP类又属于NP-Hard类的问题。它们是NP中最难的问题。

• 形式定义：一个问题$L$是NP-Complete的，当且仅当：
  1. $L\in NP$
  2. $L$是NP-Hard的
• 特点：如果能找到解决任何一个NP-Complete问题的多项式时间算法，那么所有NP问题都可以在多项式时间内解决，即P = NP。
• 例子：布尔可满足性问题（SAT）、3-SAT、顶点覆盖、Clique问题等。

复杂度类之间的关系

• $P\subseteq NP$：所有P类问题都属于NP类，因为能在多项式时间内解决的问题显然能在多项式时间内验证解的正确性。
• 如果P = NP，那么所有NP-Complete问题都可以在多项式时间内解决。
• 如果找到任一NP-Complete问题的多项式时间算法，则P = NP。
• 大多数计算机科学家相信$P\ne NP$，但这个问题仍未被证明，是计算机科学中最重要的未解问题之一。

9.1.2 多项式时间归约

多项式时间归约是证明问题NP完全性的关键技术，它建立了不同问题之间的复杂度关系。

归约的概念

问题A多项式时间归约到问题B（记为$A{\le }_{p}B$），是指存在一个多项式时间的转换算法，将A的每个实例转换为B的一个实例，且A的答案为"是"当且仅当转换后B的答案为"是"。

形式化定义：$A{\le }_{p}B$ 意味着存在函数f，使得：

1. f可以在多项式时间内计算
2. 对于任意x，$x\in A$ 当且仅当 $f(x)\in B$

归约的性质

1. 传递性：如果$A{\le }_{p}B$且$B{\le }_{p}C$，则$A{\le }_{p}C$
2. 保留多项式时间可解性：如果$A{\le }_{p}B$且$B\in P$，则$A\in P$
3. 难度传递：如果$A{\le }_{p}B$且A是NP-Hard的，则B也是NP-Hard的

归约示例：3-SAT到顶点覆盖的归约

我们可以将3-SAT问题（一种布尔可满足性问题，每个子句恰好包含3个文字）归约到顶点覆盖问题（在图中找到一个顶点子集，使得每条边至少有一个端点在子集中）。

归约过程：

1. 对于3-SAT公式中的每个变量$x_i$，创建两个顶点$v_i$和$v_i^{\prime }$，表示$x_i$和非$x_i$，并连接一条边。
2. 对于每个子句$(l_i\vee l_j\vee l_k)$，创建一个三角形，连接对应的三个文字顶点。
3. 设置顶点覆盖的大小为$n+2m$，其中$n$是变量数，$m$是子句数。

这样构造的图有顶点覆盖当且仅当原3-SAT公式可满足。

9.1.3 NP 完全性证明方法

证明一个问题是NP完全的，需要证明两点：

1. 该问题属于NP类
2. 所有NP问题都可以规约到该问题（即该问题是NP-Hard的）

证明问题属于NP类

• 需要证明对于任意"是"实例，存在一个多项式长度的证书
• 需要设计一个多项式时间的验证算法，能验证证书的正确性

例如，对于顶点覆盖问题，证书就是顶点集合本身，验证算法只需检查该集合是否覆盖了所有边。

证明问题是NP-Hard的

通常使用归约技术，从一个已知的NP完全问题A规约到待证问题B。如果能构造这样的规约，并且已知A是NP完全的，则B也是NP-Hard的。

为了进行第一个NP完全性证明，Stephen Cook在1971年直接证明了布尔可满足性问题(SAT)是NP完全的，这被称为Cook定理。

归约链

自Cook定理以来，许多问题被证明是NP完全的。通常这形成一个归约链：

SAT → 3-SAT → 顶点覆盖 → 独立集 → 团问题 → ...

通过这种方式，研究者已经识别出数百个NP完全问题。

证明示例

证明团问题（Clique Problem）是NP完全的：

1. 证明$\text{Clique}\in \text{NP}$：

   • 证书就是团中的顶点集合
   • 验证算法检查所有顶点对是否都有边相连，时间复杂度$O(n^2)$

2. 证明Clique是NP-Hard：

   • 从独立集问题规约到团问题
   • 对于图$G=(V,E)$上的独立集问题，构造图$G^{\prime }=(V,E^{\prime })$，其中$E^{\prime }$包含G中所有不存在的边
   • G中大小为k的独立集存在，当且仅当$G^{\prime }$中大小为k的团存在

9.2 典型 NP 完全问题

9.2.1 SAT 与 3-SAT

布尔可满足性问题(SAT)

定义：给定一个布尔公式，判断是否存在一种变量赋值使得公式的值为真。

例子：$(x_1\vee x_2)\wedge (\mathrm{\neg }{x}_1\vee x_3)\wedge (\mathrm{\neg }{x}_2\vee \mathrm{\neg }{x}_3)$

历史地位：SAT是第一个被证明为NP完全的问题（Cook-Levin定理）。

应用：电路设计验证、自动推理、AI规划等。

复杂性：一般的SAT问题是NP完全的，但某些特殊情形（如2-SAT，每个子句最多包含2个文字）是P类的。

3-SAT问题

定义：SAT的特例，其中每个子句恰好包含3个文字。

例子：$(x_1\vee x_2\vee \mathrm{\neg }{x}_3)\wedge (\mathrm{\neg }{x}_1\vee x_3\vee x_4)\wedge (x_2\vee \mathrm{\neg }{x}_3\vee \mathrm{\neg }{x}_4)$

复杂性：3-SAT是NP完全的，通常用作其他NP完全性证明的起点。

规约技术：可以通过引入新变量，将任意SAT公式转换为等价的3-SAT公式。

算法思路

虽然没有已知的多项式时间算法，但实际中使用的算法包括：

1. DPLL算法：基于回溯搜索，使用单元传播和纯文字消除等技术。
2. 随机化算法：如WalkSAT，结合随机走动和贪心策略。
3. 现代SAT求解器：如MiniSat、Z3等，结合冲突驱动的子句学习(CDCL)和高效的数据结构，在许多实际实例上表现良好。

9.2.2 顶点覆盖、独立集、集合覆盖

这三个经典图论问题之间有着紧密的联系。

顶点覆盖问题

定义：给定无向图$G=(V,E)$，找到最小的顶点子集$S$，使得$G$中的每条边至少有一个端点在$S$中。

NP完全性：可以从3-SAT规约得到。

近似算法：有2-近似算法（贪心选择未覆盖边的两个端点）。

应用：网络监控、资源分配。

独立集问题

定义：给定无向图$G=(V,E)$，找到最大的顶点子集$S$，使得$S$中任意两个顶点之间没有边相连。

与顶点覆盖的关系：顶点集$V$中，集合$S$是顶点覆盖，当且仅当$V-S$是独立集。

NP完全性：可以从顶点覆盖规约得到。

近似难度：除非P=NP，否则独立集问题无法在多项式时间内近似到任意常数因子。

应用：调度问题、编码理论。

集合覆盖问题

定义：给定全集$U$和$U$的子集族$F$，找到$F$的最小子集族，使其并集等于$U$。

一般化：顶点覆盖是集合覆盖的特例，其中$U$是边集，$F$是每个顶点覆盖的边组成的集合。

NP完全性：可以从顶点覆盖规约得到。

近似算法：有贪心算法，提供$\ln |U|+1$的近似比。

应用：资源选址、服务部署。

9.2.3 哈密顿回路与旅行商问题

哈密顿回路问题

定义：给定无向图$G=(V,E)$，判断是否存在一个回路，使得图中每个顶点恰好被访问一次。

NP完全性：可以从顶点覆盖规约得到。

困难实例：即使对于3-正则图（所有顶点度数为3），问题仍然是NP完全的。

特殊情况：对于特定图类（如平面图、区间图），问题可以在多项式时间内解决。

应用：电路设计、遗传学中的DNA序列拼接。

旅行商问题(TSP)

定义：给定$n$个城市和城市间的距离，找到访问每个城市恰好一次并返回起点的最短路径。

决策版本：判断是否存在总长度不超过$K$的旅行商路径。

NP完全性：哈密顿回路问题可以规约到TSP。

变种：

• 度量TSP：距离满足三角不等式，有1.5-近似算法。
• 欧几里德TSP：城市位于平面上，距离为欧几里德距离，有PTAS。

求解方法：

• 精确算法：动态规划（$O(n^2\cdot 2^n)$）、分支限界法
• 启发式算法：2-OPT、3-OPT、Lin-Kernighan算法
• 元启发式：模拟退火、遗传算法、蚁群算法

应用：物流配送、电路板钻孔、生产规划。

9.3 近似算法

对于很多NP难问题，虽然我们不能在多项式时间内找到精确解，但可以设计近似算法在合理时间内找到接近最优解的解。

9.3.1 近似因子与近似保证

近似算法的定义

近似算法是对难解问题的一种实用方法，它在多项式时间内计算出一个解，该解的质量与最优解有一定的可量化关系。

近似比的概念

对于最小化问题，如果算法A的解的值为A(I)，最优解的值为OPT(I)，则A的近似比$\rho$定义为：

$\rho (n)=max\{A(I)/OPT(I):I\text{是大小为}n\text{的实例}\}$

对于最大化问题，近似比定义为：

$\rho (n)=max\{OPT(I)/A(I):I\text{是大小为}n\text{的实例}\}$

一个$\rho$-近似算法保证其解的值与最优解相差不超过因子$\rho$。

近似方案

多项式时间近似方案(PTAS)：对于任何固定$\epsilon >0$，存在一个多项式时间算法，提供$(1+\epsilon )$-近似解。

完全多项式时间近似方案(FPTAS)：PTAS的一种，其中算法的运行时间关于输入大小$n$和$1/\epsilon$都是多项式的。

9.3.2 贪心近似算法

贪心算法是设计近似算法的常用技术，通过局部最优选择希望达到全局近似最优。

集合覆盖的贪心近似

问题：给定全集$U$和$U$的子集族$F$，找到$F$的最小子集族，使其并集等于$U$。

贪心算法：

1. 初始化$S=\mathrm{\varnothing }$，$U^{\prime }=U$
2. 当$U^{\prime }$非空时，选择覆盖$U^{\prime }$中最多元素的集合
3. 将选中的集合加入$S$，从$U^{\prime }$中移除已覆盖的元素
4. 重复步骤2-3直到$U^{\prime }$为空

近似比：$\ln |U|+1$

分析：假设最优解使用$k$个集合，每一步贪心选择至少覆盖剩余元素的$1/k$，经过数学分析可得上述近似比。

旅行商问题的2-近似

问题：度量TSP，即城市间距离满足三角不等式。

算法：

1. 计算最小生成树$T$
2. 对$T$进行先序遍历，按遍历顺序列出所有顶点
3. 按这个顺序访问所有城市并返回起点

近似比：2

分析：由三角不等式，先序遍历的总长度不超过最小生成树长度的两倍，而最小生成树长度不超过最优TSP解。

9.3.3 线性规划与随机化近似策略

线性规划松弛

许多组合优化问题可以表示为整数线性规划(ILP)。通过放松整数约束，得到线性规划(LP)，解LP后再将解"舍入"为整数解。

顶点覆盖的LP近似

LP松弛：

• 原问题：$min\sum _{v\in V}{x}_v$, subject to $x_u+x_v\ge 1$ for all $(u,v)\in E$, $x_v\in \{0,1\}$
• LP松弛：$min\sum _{v\in V}{x}_v$, subject to $x_u+x_v\ge 1$ for all $(u,v)\in E$, $0\le x_v\le 1$

舍入策略：解LP后，选择所有$x_v\ge 0.5$的顶点

近似比：2

分析：LP最优值是原问题最优值的下界，而舍入后选择的顶点数不超过LP最优值的两倍。

随机化近似

随机化算法通过引入随机性，有时可以提供比确定性算法更好的期望性能。

MAX-SAT的随机化近似

问题：给定一个CNF公式，找到一个赋值使得满足的子句数最大。

随机算法：

1. 对每个变量，随机赋值为真或假，概率各为0.5
2. 返回随机赋值结果

期望近似比：2

分析：每个子句至少有一个文字，随机赋值使该子句满足的概率至少为1/2，因此期望满足子句数不少于总子句数的一半。

随机舍入

将LP松弛与随机化结合的技术。

MAX-CUT的随机舍入：

1. 解LP松弛问题
2. 根据LP解的值，以一定概率将顶点分配到两个集合
3. 返回得到的割

Goemans-Williamson算法：使用半正定规划和随机超平面，对MAX-CUT提供0.878-近似。

9.3.4 近似算法的限制

并非所有NP难问题都有良好的近似算法。PCP定理（Probabilistically Checkable Proofs）为证明近似下界提供了强大工具。

近似难度分类

1. 存在FPTAS的问题：如背包问题
2. 存在PTAS但不存在FPTAS的问题：如欧几里德TSP
3. 存在常数近似比的问题：如顶点覆盖（2-近似）
4. 可近似到对数因子的问题：如集合覆盖
5. 除非P=NP，否则无法近似到任意常数的问题：如最大团、最长路径

无近似性结果

PCP定理的一个重要推论是：除非P=NP，否则：

• MAX-3SAT问题无法近似到优于7/8的因子
• 顶点覆盖问题无法近似到优于1.3606的因子
• 集合覆盖问题无法近似到优于$\ln n$的因子

这些结果表明某些问题的近似算法已经达到了理论最优。

9.3.5 启发式算法与元启发式

对于实际应用中的难解问题，除了近似算法，启发式算法和元启发式也是重要工具。

常见启发式方法

1. 局部搜索：从一个初始解开始，不断寻找邻域内的更优解
2. 贪心算法：基于局部最优选择构建解
3. 构造性启发式：逐步构建解，如最近邻方法解TSP

元启发式方法

1. 模拟退火：允许以一定概率接受较差解，温度逐渐降低
2. 遗传算法：模拟自然选择和遗传过程
3. 禁忌搜索：使用禁忌表避免循环
4. 蚁群算法：模拟蚂蚁寻找食物路径的过程

这些方法没有理论性能保证，但在实际应用中往往表现良好。