数据结构与算法 / 系统课时
NP 完全问题
NP 完全问题
NP 完全性并不是断言“某个问题永远无法解决”,而是刻画一类目前没有已知多项式时间通用算法的问题。本课将建立 P、NP、NP 难与 NP 完全之间的关系,并用证书验证和多项式归约说明标准证明路径。
学习目标
- 区分 P、NP、NP 难和 NP 完全的定义与关系。
- 解释证书与多项式时间验证器在 NP 定义中的作用。
- 按正确方向组织新问题的 NP 完全性证明。
问题从哪里来
许多组合问题在规模较小时可以直接搜索,但输入增长后,候选方案数量可能呈指数级膨胀。复杂性理论关注的不是某个实例能否算出,而是是否存在对所有实例都有效、运行时间受输入规模多项式约束的算法。
如果任意一个 NP 完全问题获得多项式时间算法,那么所有 NP 问题都能在多项式时间内求解。由于 P 是否等于 NP 仍未解决,不能把“尚无高效算法”写成“已证明不存在高效算法”。

核心概念
| 类别 | 判定含义 | 关键说明 |
|---|---|---|
| P | 存在确定性多项式时间算法可以求解 | 通常作为“高效可解”的理论基准 |
| NP | 给定候选证书后,可在多项式时间内验证 | NP 不表示“非多项式” |
| NP 难 | 每个 NP 问题都能在多项式时间内归约到它 | 不要求该问题属于 NP,也不要求它是判定问题 |
| NP 完全 | 同时属于 NP 且是 NP 难 | 是 NP 中最难的一类判定问题 |
判定问题只回答“是”或“否”。例如,优化版旅行商问题要求最短回路,而对应判定版询问“是否存在长度不超过 的回路”。讨论 NP 完全性时,通常先把问题写成判定形式。
NP 中的“可验证”可以用证书理解。对子集和问题,证书可以是一组被选中的数组下标;验证器只需检查下标合法且对应元素之和等于目标值。验证器不负责寻找证书,因此“容易验证”不等于“容易求解”。
证明 NP 完全的一般步骤
- 把待证明问题 B 明确定义为判定问题,并说明输入规模。
- 证明 B 属于 NP:给出证书形式和多项式时间验证过程。
- 选择一个已知 NP 完全问题 A。
- 构造多项式时间变换,把 A 的任意实例映射为 B 的实例。
- 证明当且仅当关系:A 的实例回答“是”,映射后的 B 实例也回答“是”。
- 说明变换时间为多项式,从而得到 。
归约方向不能写反。为了证明 B 至少和 A 一样难,必须把已知困难的 A 归约到待证明的 B。若 B 有高效算法,就可以先完成变换,再调用该算法解决 A。
可运行示例
下面的 Python 程序演示子集和问题的证书验证器。它不搜索答案,只检查外部给出的下标集合是否构成合法证书。
def verify_subset_sum(numbers, target, certificate):
# 证书使用数组下标表示被选择的元素,并禁止重复选择同一位置。
if len(set(certificate)) != len(certificate):
return False
if any(index < 0 or index >= len(numbers) for index in certificate):
return False
return sum(numbers[index] for index in certificate) == target
def main():
numbers = [3, 7, 11, 15]
target = 18
print("有效证书:", verify_subset_sum(numbers, target, [1, 2]))
print("无效证书:", verify_subset_sum(numbers, target, [0, 1]))
if __name__ == "__main__":
main()保存为 np_verifier_demo.py 后运行:
python np_verifier_demo.py预期输出
有效证书: True
无效证书: False设证书包含 个下标,求和与合法性检查都可在多项式时间内完成。这个示例展示的是“属于 NP”的验证思想,不构成对子集和问题的多项式时间求解算法。
常见错误
- 把 NP 解释为“不能在多项式时间求解”。正确含义是“可以在多项式时间验证证书”。
- 只证明问题属于 NP 就宣布它 NP 完全。还必须证明它是 NP 难。
- 使用 证明 B 很难。这个方向不能推出 B 为 NP 难。
- 只描述映射直觉,不证明“是实例”双向等价,也不分析构造时间。
本课练习
- 对“给定无向图和整数 ,是否存在大小至少为 的团”写出证书和验证步骤。验收条件是说明每项检查的时间复杂度,并证明总时间为输入规模的多项式。
- 假设 3-SAT 已知为 NP 完全,为一个待证明问题列出完整证明清单。验收条件是明确归约方向、实例映射、双向正确性和构造复杂度,不需要给出具体映射。
本课总结
- NP 描述证书可在多项式时间内验证,NP 完全同时满足“属于 NP”和“是 NP 难”。
- 多项式归约通过保持判定答案,把已知困难问题的求解能力转移到新问题。
- 证明中的关键检查点是归约方向、双向等价和变换复杂度。
下一课预告
下一课将学习“随机化算法”,比较拉斯维加斯算法与蒙特卡洛算法,并分析随机选择如何改善快速排序的期望表现。