P 对 NP 问题的提出

1971年库克形式化NP完全性并提出P对NP问题，成为理论计算机科学核心难题。

时代: 当代
文明 / 地域: 北美

背景

随着计算机科学的兴起，需要严格界定”容易求解”与”容易验证”之间的界限，并理解二者是否等同。

详细描述

1971年，斯蒂芬·库克（Stephen Cook）在论文《定理证明程序的复杂性》中形式化了多项式时间可归约（Cook归约）与NP完全性，并证明布尔可满足性问题（SAT）是NP完全的。由此他提出著名的P对NP问题：是否每个”解可被多项式时间验证”的问题，也都”可被多项式时间求解”？即 $P=NP$ 是否成立？

列文（Leonid Levin）在苏联独立得到相同结论，合称库克–列文定理。 $P$ 指确定性图灵机在多项式时间内可解的问题类， $NP$ 指给定解可在多项式时间内验证的问题类。

求解过程 / 影响（含最新进展若相关）

P对NP是理论计算机科学最核心的开放问题，被列为”千禧年七大难题”之一（官方陈述由Cook本人撰写）。若 $P=NP$ ，将对密码学（如大数分解、离散对数）、优化与运筹产生颠覆性影响；目前主流观点（含库克本人）猜想 $P\neq NP$ 。1972年卡普（Richard Karp）证明21个经典问题均为NP完全，此后数千问题被归入此类。它在算法设计、计算复杂性、密码学与人工智能中影响深远。