斯蒂芬·库克（Stephen Cook）

斯蒂芬·库克（Stephen Cook）是加拿大多伦多大学教授、计算机科学家，因奠定计算复杂性理论、首次提出NP完全性而获得1982年图灵奖。

概述

库克1939年生于美国纽约州，后在多伦多大学长期任教。1971年他发表论文，证明布尔可满足性问题是NP完全的，即所有NP类问题都可在多项式时间内归约到它。这一被称为库克定理的结果，第一次给出了衡量问题内在难度的严格框架，也直接引出了著名的P是否等于NP问题。

核心贡献

• 库克定理：证明可满足性问题的NP完全性，开创复杂性分类研究。
• P与NP问题：提出这一核心猜想，被列为千禧年七大数学难题之一。
• 证明复杂性与命题证明系统的研究。
• 推动将资源受限计算作为独立学科加以研究。

应用场景

库克的理论为密码学提供了安全性基础，许多加密体制正是建立在某些问题难以高效求解的假设之上。它也指导算法设计者合理设置目标：面对NP完全问题时选择近似或启发式方法。可满足性求解器如今被用于芯片验证、软件测试与自动规划。

常见问题

问：P等于NP会带来什么后果？答：如果被证明相等，意味着大量困难问题都存在高效算法，将颠覆密码学和优化领域；多数学者相信二者不相等，但至今无人证明。

问：可满足性问题为何如此重要？答：因为它是第一个被证明的NP完全问题，其他众多问题都可归约到它，所以它成为衡量计算难度的基准和研究复杂性的入口。