算法分析与设计

Appearance

8.2 P与NP——复杂性类的直觉定义 ​

问题：哪些问题能在多项式时间内解决？哪些只能验证？

面试难题 ​

"排序问题在P中吗？TSP问题在P中吗？"

这是算法面试中常见的问题。要回答它，我们需要理解P和NP的精确含义。

先给出直觉答案：

  • 排序问题：在P中——归并排序O(n log n)，快速排序平均O(n log n)
  • TSP问题：不知道是否在P中——目前没有多项式时间算法

但为什么"不知道"比"不在"更准确？这涉及到复杂性类的精确定义。

一个类比：储蓄账户 vs 股票市场 ​

理解P和NP的一个直观方式：

P类问题 = 储蓄账户 ​

特征：

  • 存入100元，确定能得到100元+利息
  • 收益可预测、稳定
  • 多项式时间内保证能解决

例子：

  • 排序：归并排序O(n log n)
  • 最短路：Dijkstra O(E log V)
  • 矩阵乘法：O(n^2.373)

为什么"稳定"？

  • 算法运行时间可预测
  • 对于规模n，知道最坏情况下需要多少步
  • 可以保证在合理时间内完成

NP类问题 = 股票市场 ​

特征：

  • 投入100元，可能变成200元，也可能变成50元
  • 收益不确定、高风险
  • 多项式时间内可能解决，也可能无解

例子：

  • SAT：布尔可满足性
  • TSP：旅行商问题
  • 顶点覆盖：找最小覆盖集

为什么"不确定"？

  • 如果有解，可以在多项式时间内验证
  • 但不知道是否能快速找到解
  • 可能需要指数时间穷举

P=NP问题 = 储蓄账户是否等价于股票市场？ ​

含义：

  • 如果P=NP：股票市场可以像储蓄账户一样稳定收益
  • 如果P≠NP：两者本质不同

大多数计算机科学家相信P≠NP，但至今尚未证明。

形式化定义 ​

确定性图灵机 ​

确定性图灵机（DTM）是计算的抽象模型：

  • 读写头
  • 无限长的纸带
  • 状态转移规则（确定性）

关键特征：每一步的下一步是确定的。

非确定性图灵机 ​

非确定性图灵机（NTM）：

  • 每一步可以"猜"多个分支
  • 如果存在一条路径导致接受，则接受

关键特征：可以"猜"正确答案，然后验证。

P类（多项式时间） ​

定义：P类是所有能在确定性图灵机上用多项式时间解决的判定问题集合。

P = {问题L | 存在多项式时间算法A，使得对于所有输入x：
     A(x) = L(x)}

更通俗地说：

  • P = 多项式时间可解的问题
  • "解" = 找到答案，不需要猜测

NP类（非确定性多项式时间） ​

定义：NP类是所有能在非确定性图灵机上用多项式时间解决的判定问题集合。

等价定义（更实用）：

NP = {问题L | 存在多项式时间验证器V和多项式p，使得：
     对于所有输入x，L(x) = 1 当且仅当 
     存在证书c，|c| ≤ p(|x|)，V(x, c) = 1}

更通俗地说：

  • NP = 多项式时间可验证的问题
  • "验证" = 给定答案，检查正确性

关键定理 ​

定理：NP = 多项式时间可验证的判定问题集合

证明思路：

  • 如果非确定性图灵机能解，则存在多项式验证器（证书=猜的路径）
  • 如果存在多项式验证器，则非确定性图灵机能猜证书并验证

P ⊆ NP ​

显然P ⊆ NP：

  • 能解的问题一定能验证
  • 不需要猜，直接算出答案，然后"验证"就是比较答案

问题是：NP ⊆ P吗？即P=NP吗？

复杂性类关系图 ​

假设P≠NP，各类的关系如下：

                    PSPACE
               ┌────────────────┐
               │                │
               │   ┌────────┐   │
               │   │  NP    │   │
               │   │ ┌────┐ │   │
               │   │ │NP-c│ │   │         co-NP
               │   │ │SAT │ │   │      ┌────────┐
               │   │ └────┘ │   │      │        │
               │   │   P    │   │      │        │
               │   │ ┌────┐ │   │      │        │
               │   │ │排序│ │   │      │        │
               │   │ └────┘ │   │      │        │
               │   └────────┘   │      └────────┘
               └────────────────┘

各层含义：

类定义例子
P多项式时间可解排序、最短路、矩阵乘法
NP多项式时间可验证SAT、TSP、顶点覆盖
NP-completeNP中最难的问题SAT、3-SAT、顶点覆盖、团问题
NP-hard至少和NP-complete一样难TSP优化版本、停机问题
co-NPNP问题的补问题不可满足性、非哈密顿性
PSPACE多项式空间可解广义棋类、量词布尔公式

关键定理：如果任何一个NP-complete问题在P中，则P=NP。

如何判断问题属于哪个类？ ​

判断P类 ​

问：是否存在多项式时间算法？

方法：

  1. 设计算法
  2. 分析时间复杂度
  3. 确认是多项式

例子：排序

  • 归并排序：O(n log n)
  • 确认：n log n是多项式
  • 结论：排序在P中

判断NP类 ​

问：给定答案，能否在多项式时间内验证？

方法：

  1. 定义证书的形式
  2. 设计验证器
  3. 分析验证时间

例子：SAT

  • 证书：变量赋值
  • 验证器：代入公式，计算真值
  • 时间：O(子句数 × 变量数)
  • 结论：SAT在NP中

判断NP-complete ​

问：

  1. 是否在NP中？
  2. 所有NP问题能否归约到它？

方法：

  1. 证明在NP中
  2. 选择已知NP-complete问题
  3. 设计多项式时间归约

我们将在后面的章节详细讨论这个过程。

常见误解澄清 ​

误解1：NP = "非多项式" ​

错误！NP = "非确定性多项式时间"，不是"非多项式"。

NP问题是多项式时间可验证的问题，可能多项式可解，也可能不是。

误解2：NP问题"很慢" ​

错误！NP问题本身不慢，"慢"的是我们目前知道的算法。

例如：

  • 线性规划曾被认为指数时间，后来发现多项式时间算法
  • 素数判定曾被认为没有多项式时间算法，2002年AKS算法证明在P中

误解3：如果P≠NP，NP问题就无法有效解决 ​

错误！P≠NP只意味着没有多项式时间的精确算法。

实际上我们有：

  • 近似算法：有质量保证的近似解
  • 启发式方法：实践中效果好
  • 特殊情况：很多NP问题在特殊情况下多项式可解

练习 ​

基础练习 ​

  1. 判断复杂性类

    判断以下问题属于P还是NP：

    a) 最长公共子序列问题 b) 图着色问题（判断能否用k种颜色） c) 子集和问题（判断是否存在子集和等于目标值） d) 二分图匹配问题

  2. 考试类比

    用"考试"类比解释P和NP：

    • P类问题相当于什么？
    • NP类问题相当于什么？
    • NP-complete问题相当于什么？

进阶练习 ​

  1. 素数判定

    素数判定问题：给定正整数n，判断n是否为素数。

    a) 这个问题为什么在NP中？ b) 这个问题为什么在P中？（提示：AKS算法） c) 这个例子说明了什么？

  2. 复杂性类关系

    证明：如果P=NP，则co-NP=NP。

    （提示：考虑补问题的定义）

思考题 ​

  1. NP的定义

    为什么NP定义为"多项式时间可验证"而不是"多项式时间可解"？ 这个定义有什么深刻含义？

  2. P=NP的意义

    如果P=NP，密码学、优化、AI会发生什么变化？ 请列举具体影响并讨论其后果。

小结 ​

概念定义直觉理解
P多项式时间可解储蓄账户——稳定、可预测
NP多项式时间可验证股票市场——不确定、有风险
NP-completeNP中最难的问题基准问题——代表整个NP类
NP-hard至少和NP-complete一样难更难的问题——不一定在NP中
P≠NP猜想验证容易≠发现容易

核心洞见：P和NP定义了计算的边界。P类问题是"容易"的，NP类问题是"可能难"的，NP-complete是"最难"的NP问题。

下一节：我们将学习NP完全性和Cook定理，理解为什么存在"最难"的NP问题。

新时代的算法课程