知识/定理
库克（1971）定义 NP 完全性，提出 P vs NP 问题——是否「易验证」=「易求解」。
公式
SAT 是 NP 完全；$P=NP$? 千禧年问题，未知。
证明思路
（归约）把一切 NP 问题多项式归约到 SAT，确立「最难 NP 问题」类。
应用/例子
密码学（若 P=NP 则公钥密码崩溃）、优化、调度、人工智能。
意义/影响
计算机科学最重要开放问题；「验证易 ≠ 求解易」的数学化。
DOXA · 数学编年史 · 知识详情
1971 ｜ 库克 ｜ 离散·组合 ｜ 突破
库克（1971）定义 NP 完全性，提出 P vs NP 问题——是否「易验证」=「易求解」。
SAT 是 NP 完全；$P=NP$? 千禧年问题，未知。
（归约）把一切 NP 问题多项式归约到 SAT，确立「最难 NP 问题」类。
密码学（若 P=NP 则公钥密码崩溃）、优化、调度、人工智能。
计算机科学最重要开放问题；「验证易 ≠ 求解易」的数学化。