Chap8 NP 与计算困难性

返回：0400 算法设计与分析总目录 · 上一章：0407 Chap7 网络流 · 下一章：0409 Chap9 近似算法

1、学习目标

前面几章都在寻找高效算法，本章开始问另一个问题：如果一直找不到高效算法，是不是问题本身就很难？

模块	要掌握的内容
P	多项式时间可解问题
NP	给定证书后可在多项式时间验证
规约	用一个问题求解另一个问题
NP 完全	NP 中最难的一批问题
NP 困难	至少和 NP 完全问题一样难
证明方法	从已知 NP 完全问题多项式规约

2、判定问题

复杂性理论通常先讨论判定问题，也就是答案为 yes/no 的问题。

优化问题：

求最短 Hamilton 回路长度

判定版本：

是否存在长度不超过 K 的 Hamilton 回路？

很多优化问题可以转成判定问题来讨论难度。

3、P 与 NP

类	含义
P	能在多项式时间内求解
NP	给定一个候选解，能在多项式时间内验证

例子：

SAT：给定布尔公式，是否存在赋值使公式为真？

如果有人给出一组赋值，我们可以快速检查公式是否为真，所以 SAT 属于 NP。

注意：

NP 不是 non-polynomial，而是 nondeterministic polynomial。

4、多项式规约

若问题 A 可以多项式时间规约到问题 B，记作：

A <=p B

意思是：

如果我会高效解决 B，就能高效解决 A。

规约方向很重要：

想证明	应该做什么
B 很难	从已知难问题 A 规约到 B
A 可解	把 A 规约到已知可解问题 B

证明 NP 完全时，最常犯的错误就是规约方向反了。

5、NP 完全与 NP 困难

一个问题 X 是 NP 完全，需要满足：

1. X 属于 NP。
2. 任意 NP 问题都能多项式规约到 X。

实际证明时通常：

1. 证明 X 属于 NP。
2. 选一个已知 NP 完全问题 Y。
3. 证明 Y <=p X。

NP 困难只要求第二部分的难度，不要求问题属于 NP。

6、典型 NP 完全问题

问题	形式
SAT	布尔公式是否可满足
3-SAT	每个子句 3 个文字的 SAT
Vertex Cover	是否存在大小不超过 k 的点覆盖
Independent Set	是否存在大小至少 k 的独立集
Clique	是否存在大小至少 k 的团
Hamilton Cycle	是否存在 Hamilton 回路
Subset Sum	是否存在子集和为目标值
TSP 判定版	是否存在长度不超过 K 的巡回路

这些问题之间可以互相规约，形成一张“困难性地图”。

7、规约证明模板

证明 Y <=p X：

1. 从 Y 的任意实例出发。
2. 在多项式时间构造一个 X 的实例。
3. 证明若 Y 实例为 yes，则构造出的 X 实例为 yes。
4. 证明若构造出的 X 实例为 yes，则原 Y 实例为 yes。
5. 说明构造规模是多项式。

核心是双向等价：

Y has solution  <=>  X has solution

8、优化问题怎么办

如果一个优化问题的判定版本是 NP 完全，通常说明精确求最优值也不会容易。

比如 TSP：

1. 优化版：求最短巡回路。
2. 判定版：是否存在长度不超过 K 的巡回路。

如果能多项式时间求优化版，就能多项式时间回答判定版。因此判定版困难会暗示优化版困难。

9、co-NP

co-NP 是“否定问题”的可验证类。

若问题 L 在 NP 中，则它的补问题在 co-NP 中。

例：

SAT：是否存在满足赋值？
UNSAT：是否对所有赋值都不满足？

给 SAT 的 yes 证书是一组满足赋值；但给 UNSAT 的 yes 证书就不容易，因为要说明所有赋值都失败。

10、学这章的意义

复杂性理论不是为了让人放弃，而是为了指导策略：

判断	应对
问题在 P	继续寻找精确高效算法
问题 NP 完全	不盲目追求通用精确多项式算法
实例规模小	回溯、分支限界、搜索优化
可接受误差	近似算法
可接受概率	随机算法
特殊结构	利用图形、参数、约束范围

11、易错点

易错点	修正
NP 理解成非多项式	NP 是可多项式验证
规约方向写反	证明新问题难，要从已知难问题规约过来
只证明 NP-hard	NP 完全还要证明属于 NP
优化问题直接说 NP 完全	通常先转判定版本
把没找到算法当成 NP 完全	需要严格规约证明

12、复盘清单

检查项	状态
能区分 P、NP、NP-hard、NP-complete	待复盘
能解释证书和验证器	待复盘
能写出多项式规约的含义	待复盘
能说明证明 NP 完全的两步	待复盘
能举出 3 个典型 NP 完全问题	待复盘