数据结构与算法 / 系统课时
P 类与 NP 类
P 类与 NP 类
当问题规模不断增大时,真正关键的不只是“能不能求出答案”,还包括“能否在合理时间内验证一个候选答案”。本课从判定问题出发,建立 P 类、NP 类、证书与验证算法之间的准确关系。
学习目标
- 理解多项式时间与判定问题的含义。
- 说明 NP 类中的证书和多项式时间验证器。
- 区分“容易求解”“容易验证”和“尚未知是否容易求解”。
从求解到验证
复杂性理论通常先研究答案只有“是”或“否”的判定问题。若存在一个确定性算法,能在输入规模 的多项式时间内完成判定,例如 、 或 ,该问题属于 P 类。
NP 类关注验证过程。对每个答案为“是”的实例,如果都存在一个长度至多为输入规模多项式的证书,并且验证器能在多项式时间内确认该证书有效,那么该问题属于 NP 类。证书可以是一组被选中的顶点、一条访问所有顶点的回路,或满足目标和的元素下标。

| 类别 | 核心要求 | 关注点 | 典型表述 |
|---|---|---|---|
| P | 能在多项式时间内求解 | 求解速度 | “我能快速算出答案” |
| NP | “是”实例的证书能在多项式时间内验证 | 验证速度 | “给我候选答案,我能快速检查” |
因为能快速求解的问题当然也能快速验证,所以 P ⊆ NP。反方向是否成立,即 P = NP,仍是计算机科学中的开放问题。NP 不是“非多项式时间”的缩写,也不等同于“绝对无法求解”。
核心边界与例子
最短路径判定问题“是否存在长度不超过 的路径”属于 P,因为可以直接运行最短路径算法后比较结果。哈密顿回路判定问题属于 NP:证书是一条顶点序列,验证器只需检查每个顶点是否恰好出现一次、相邻顶点之间是否有边,以及首尾是否相连。
需要特别注意,证明一个问题属于 NP,只说明有效证书可以被快速验证,并没有给出快速求解算法。暴力搜索所有证书通常仍可能需要指数时间。
完整可运行示例
下面用子集和判定问题演示证书验证。输入给出整数数组和目标值,证书给出被选择元素的下标。验证器检查下标是否合法、是否重复,以及对应元素之和是否等于目标值。
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()运行命令:
python p_np_verifier.py预期输出:
证书 [1, 2] 是否有效: True
证书 [0, 2] 是否有效: False设证书包含 个下标,验证过程的时间复杂度为 ,空间复杂度为 ,额外空间主要用于检测重复下标。这个验证器说明子集和问题的“是”实例可以被快速验证,但不意味着已经找到多项式时间求解算法。
易混淆点与练习
常见错误之一是把 NP 理解为“不能在多项式时间内解决”。准确说法是:NP 问题至少能在多项式时间内验证“是”证书,其中一部分问题已经知道属于 P。另一个错误是只检查证书计算出的结果,却不检查证书格式和边界,这会让非法下标或重复元素绕过验证规则。
练习 1:为“图中是否存在大小至少为 的团”设计证书格式,并列出验证器必须执行的检查。验收条件是能说明证书长度为何是多项式级,并给出验证复杂度。
练习 2:修改示例,使证书直接包含被选中的数值而不是下标。分析当数组存在重复值时会产生什么歧义,并提出不会误判的证书设计。
本课总结
- P 类要求问题本身能在多项式时间内求解,NP 类要求“是”证书能在多项式时间内验证。
- P ⊆ NP,但目前不知道 P 是否等于 NP。
- 验证算法必须同时检查证书内容、格式与边界,快速验证不等于快速求解。
下一课预告
下一课将学习“多项式时间归约”,通过把一个问题实例高效转换为另一个问题实例,比较不同问题的计算难度并建立 NP 完全性证明的基础。