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

P 类与 NP 类

P 类与 NP 类

当问题规模不断增大时,真正关键的不只是“能不能求出答案”,还包括“能否在合理时间内验证一个候选答案”。本课从判定问题出发,建立 P 类、NP 类、证书与验证算法之间的准确关系。

学习目标

  • 理解多项式时间与判定问题的含义。
  • 说明 NP 类中的证书和多项式时间验证器。
  • 区分“容易求解”“容易验证”和“尚未知是否容易求解”。

从求解到验证

复杂性理论通常先研究答案只有“是”或“否”的判定问题。若存在一个确定性算法,能在输入规模 nn 的多项式时间内完成判定,例如 O(n)O(n)、O(n2)O(n^2) 或 O(n3)O(n^3),该问题属于 P 类。

NP 类关注验证过程。对每个答案为“是”的实例,如果都存在一个长度至多为输入规模多项式的证书,并且验证器能在多项式时间内确认该证书有效,那么该问题属于 NP 类。证书可以是一组被选中的顶点、一条访问所有顶点的回路,或满足目标和的元素下标。

P 类、NP 类与证书验证关系

类别 核心要求 关注点 典型表述
P 能在多项式时间内求解 求解速度 “我能快速算出答案”
NP “是”实例的证书能在多项式时间内验证 验证速度 “给我候选答案,我能快速检查”

因为能快速求解的问题当然也能快速验证,所以 P ⊆ NP。反方向是否成立,即 P = NP,仍是计算机科学中的开放问题。NP 不是“非多项式时间”的缩写,也不等同于“绝对无法求解”。

核心边界与例子

最短路径判定问题“是否存在长度不超过 LL 的路径”属于 P,因为可以直接运行最短路径算法后比较结果。哈密顿回路判定问题属于 NP:证书是一条顶点序列,验证器只需检查每个顶点是否恰好出现一次、相邻顶点之间是否有边,以及首尾是否相连。

需要特别注意,证明一个问题属于 NP,只说明有效证书可以被快速验证,并没有给出快速求解算法。暴力搜索所有证书通常仍可能需要指数时间。

完整可运行示例

下面用子集和判定问题演示证书验证。输入给出整数数组和目标值,证书给出被选择元素的下标。验证器检查下标是否合法、是否重复,以及对应元素之和是否等于目标值。

python
from typing import Sequence

def verify_subset_sum(
    numbers: Sequence[int],
    target: int,
    certificate: Sequence[int],
) -> bool:
    # 重复下标会把同一个元素使用多次,因此直接拒绝。
    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() -> None:
    numbers = [3, 7, 11, 15]
    target = 18

    valid_certificate = [1, 2]
    invalid_certificate = [0, 2]

    print(
        f"证书 {valid_certificate} 是否有效: "
        f"{verify_subset_sum(numbers, target, valid_certificate)}"
    )
    print(
        f"证书 {invalid_certificate} 是否有效: "
        f"{verify_subset_sum(numbers, target, invalid_certificate)}"
    )

if __name__ == "__main__":
    main()

运行命令:

bash
python p_np_verifier.py

预期输出:

text
证书 [1, 2] 是否有效: True
证书 [0, 2] 是否有效: False

设证书包含 mm 个下标,验证过程的时间复杂度为 O(m)O(m),空间复杂度为 O(m)O(m),额外空间主要用于检测重复下标。这个验证器说明子集和问题的“是”实例可以被快速验证,但不意味着已经找到多项式时间求解算法。

易混淆点与练习

常见错误之一是把 NP 理解为“不能在多项式时间内解决”。准确说法是:NP 问题至少能在多项式时间内验证“是”证书,其中一部分问题已经知道属于 P。另一个错误是只检查证书计算出的结果,却不检查证书格式和边界,这会让非法下标或重复元素绕过验证规则。

练习 1:为“图中是否存在大小至少为 kk 的团”设计证书格式,并列出验证器必须执行的检查。验收条件是能说明证书长度为何是多项式级,并给出验证复杂度。

练习 2:修改示例,使证书直接包含被选中的数值而不是下标。分析当数组存在重复值时会产生什么歧义,并提出不会误判的证书设计。

本课总结

  • P 类要求问题本身能在多项式时间内求解,NP 类要求“是”证书能在多项式时间内验证。
  • P ⊆ NP,但目前不知道 P 是否等于 NP。
  • 验证算法必须同时检查证书内容、格式与边界,快速验证不等于快速求解。

下一课预告

下一课将学习“多项式时间归约”,通过把一个问题实例高效转换为另一个问题实例,比较不同问题的计算难度并建立 NP 完全性证明的基础。

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

目录与阅读设置

阅读设置

17

记录一个想法

P 类与 NP 类

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

登录哪都通