01 · 计算人生
成果背后的人
斯蒂芬·库克为比较计算问题的难度提供了精确方法。他证明布尔可满足性问题是 NP 完全的，即 NP 中的每个问题都可以高效转化为它。他在多伦多大学的研究推动复杂性理论成为理解可行计算的基础。这一结果并未解决 P 是否等于 NP；两者仍是不同的问题。
理解这项贡献
斯蒂芬·库克通过揭示布尔可满足性问题的特殊地位，奠定了 NP 完全性的基础。NP 问题的候选解能够被高效检验。他的结果表明，这一类中的每个问题都能以多项式级别的额外代价转化为可满足性问题。
为什么重要
归约揭示了许多搜索问题背后的共同结构，帮助解释寻找精确解为何困难。