斯蒂芬·库克
活跃于约1939年, 美国纽约州布法罗
数学基础应用与计算数学
美裔加拿大计算机科学家兼数学家,创立了NP完全性理论,提出P与NP问题并证明了库克-列文定理。
斯蒂芬·库克生于纽约州布法罗,1966年在哈佛大学获得数学博士学位。在加州大学伯克利分校担任助理教授后,他于1970年加入多伦多大学,此后一直在此工作并加入加拿大国籍。
库克1971年的论文《定理证明过程的复杂性》引入了NP完全性的概念,并证明布尔可满足性问题(SAT)是NP完全的——即库克-列文定理,苏联的列昂尼德·列文也独立发现了这一结果。该论文提出了后来的P与NP问题:凡是能快速验证解的问题是否也能快速求解。这开创了计算复杂性理论这一领域,至今仍是克莱数学研究所七个千禧年大奖难题之一,尚未解决。
因这一工作,库克获得1982年ACM图灵奖,这是计算机科学的最高荣誉。他此后一直在多伦多大学从事复杂性理论与证明复杂性研究,现为该校荣休教授。
工作单位: 加州大学伯克利分校, 多伦多大学
加拿大, 美国