数据结构与算法 / 系统课时

NP 完全问题

NP 完全问题

NP 完全性并不是断言“某个问题永远无法解决”,而是刻画一类目前没有已知多项式时间通用算法的问题。本课将建立 P、NP、NP 难与 NP 完全之间的关系,并用证书验证和多项式归约说明标准证明路径。

学习目标

  • 区分 P、NP、NP 难和 NP 完全的定义与关系。
  • 解释证书与多项式时间验证器在 NP 定义中的作用。
  • 按正确方向组织新问题的 NP 完全性证明。

问题从哪里来

许多组合问题在规模较小时可以直接搜索,但输入增长后,候选方案数量可能呈指数级膨胀。复杂性理论关注的不是某个实例能否算出,而是是否存在对所有实例都有效、运行时间受输入规模多项式约束的算法。

如果任意一个 NP 完全问题获得多项式时间算法,那么所有 NP 问题都能在多项式时间内求解。由于 P 是否等于 NP 仍未解决,不能把“尚无高效算法”写成“已证明不存在高效算法”。

P、NP、NP 难与 NP 完全的关系及归约证明流程

核心概念

类别 判定含义 关键说明
P 存在确定性多项式时间算法可以求解 通常作为“高效可解”的理论基准
NP 给定候选证书后,可在多项式时间内验证 NP 不表示“非多项式”
NP 难 每个 NP 问题都能在多项式时间内归约到它 不要求该问题属于 NP,也不要求它是判定问题
NP 完全 同时属于 NP 且是 NP 难 是 NP 中最难的一类判定问题

判定问题只回答“是”或“否”。例如,优化版旅行商问题要求最短回路,而对应判定版询问“是否存在长度不超过 KK 的回路”。讨论 NP 完全性时,通常先把问题写成判定形式。

NP 中的“可验证”可以用证书理解。对子集和问题,证书可以是一组被选中的数组下标;验证器只需检查下标合法且对应元素之和等于目标值。验证器不负责寻找证书,因此“容易验证”不等于“容易求解”。

证明 NP 完全的一般步骤

  1. 把待证明问题 B 明确定义为判定问题,并说明输入规模。
  2. 证明 B 属于 NP:给出证书形式和多项式时间验证过程。
  3. 选择一个已知 NP 完全问题 A。
  4. 构造多项式时间变换,把 A 的任意实例映射为 B 的实例。
  5. 证明当且仅当关系:A 的实例回答“是”,映射后的 B 实例也回答“是”。
  6. 说明变换时间为多项式,从而得到 A≤pBA \leq_p B。

归约方向不能写反。为了证明 B 至少和 A 一样难,必须把已知困难的 A 归约到待证明的 B。若 B 有高效算法,就可以先完成变换,再调用该算法解决 A。

可运行示例

下面的 Python 程序演示子集和问题的证书验证器。它不搜索答案,只检查外部给出的下标集合是否构成合法证书。

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 后运行:

bash
python np_verifier_demo.py

预期输出

text
有效证书: True
无效证书: False

设证书包含 kk 个下标,求和与合法性检查都可在多项式时间内完成。这个示例展示的是“属于 NP”的验证思想,不构成对子集和问题的多项式时间求解算法。

常见错误

  • 把 NP 解释为“不能在多项式时间求解”。正确含义是“可以在多项式时间验证证书”。
  • 只证明问题属于 NP 就宣布它 NP 完全。还必须证明它是 NP 难。
  • 使用 B≤pAB \leq_p A 证明 B 很难。这个方向不能推出 B 为 NP 难。
  • 只描述映射直觉,不证明“是实例”双向等价,也不分析构造时间。

本课练习

  1. 对“给定无向图和整数 kk,是否存在大小至少为 kk 的团”写出证书和验证步骤。验收条件是说明每项检查的时间复杂度,并证明总时间为输入规模的多项式。
  2. 假设 3-SAT 已知为 NP 完全,为一个待证明问题列出完整证明清单。验收条件是明确归约方向、实例映射、双向正确性和构造复杂度,不需要给出具体映射。

本课总结

  • NP 描述证书可在多项式时间内验证,NP 完全同时满足“属于 NP”和“是 NP 难”。
  • 多项式归约通过保持判定答案,把已知困难问题的求解能力转移到新问题。
  • 证明中的关键检查点是归约方向、双向等价和变换复杂度。

下一课预告

下一课将学习“随机化算法”,比较拉斯维加斯算法与蒙特卡洛算法,并分析随机选择如何改善快速排序的期望表现。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

NP 完全问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通