1982 · 理论与算法

检查答案，可能比寻找更容易

NP 完全性把看似不同的困难问题联系起来。

斯蒂芬·库克

1982图灵奖

视觉指南

奖项，化为图解

阅读图解文字

归约揭示了许多搜索问题背后的共同结构，帮助解释寻找精确解为何困难。

NP 完全性不意味着每个实例都难，也没有解决 P 是否等于 NP。

01 · 核心想法

斯蒂芬·库克通过揭示布尔可满足性问题的特殊地位，奠定了 NP 完全性的基础。NP 问题的候选解能够被高效检验。他的结果表明，这一类中的每个问题都能以多项式级别的额外代价转化为可满足性问题。

归约揭示了许多搜索问题背后的共同结构，帮助解释寻找精确解为何困难。

02 · 人物

斯蒂芬·库克为比较计算问题的难度提供了精确方法。他证明布尔可满足性问题是 NP 完全的，即 NP 中的每个问题都可以高效转化为它。他在多伦多大学的研究推动复杂性理论成为理解可行计算的基础。这一结果并未解决 P 是否等于 NP；两者仍是不同的问题。

03 · 延伸阅读

本站原创讲解依据官方获奖记录。领域标签用于编辑导航。