NP完全问题

概述

NP完全问题 是NP类中”最难”的问题子集，已知没有多项式时间算法。P vs NP 问题是计算机科学最核心的开放问题之一。

定义

NP完全问题

一个判定问题 $L$ 是NP完全的，当且仅当：(1) $L\in \text{NP}$（给定证书可在多项式时间内验证）；(2) 所有NP问题都可多项式时间归约到 $L$。

核心性质

• NP类：可在多项式时间内验证解的问题类（不要求在多项式时间内找到解）
• P类：可在多项式时间内求解的问题类。显然 $P\subseteq \text{NP}$
• P vs NP：$P\stackrel{?}{=}\text{NP}$ 是千禧年七大数学难题之一，悬赏一百万美元
• Cook-Levin定理：布尔可满足性问题（SAT）是第一个被证明为NP完全的问题
• 归约：若问题A可多项式归约到问题B，则B至少和A一样难。NP完全问题之间可以互相归约
• 实际意义：NP完全问题广泛出现在调度、图论、优化等领域，实践中常采用近似算法或启发式方法

章节扩展

第1章：NP完全性展示了算法能力的边界——并非所有问题都有高效解法。第34章将系统讨论NP完全性理论。

参见

• 1.1 算法 — 算法的基本定义与效率概念