未解决问题，应用与计算数学, 数学基础，1971年提出
P与NP问题
未解决千禧年
设 P 为可由确定性算法在输入规模的多项式时间内求解的判定问题类,NP 为所提出的解可在多项式时间内验证的判定问题类。问题是 P 是否等于 NP:每一个能被高效验证的问题,是否也存在高效的求解算法?
截至2026年,P与NP问题仍未解决,大多数计算机科学家猜测 P ≠ NP。数十年的研究揭示了一些形式化障碍——相对化(贝克-吉尔-索洛维,1975年)、自然证明(拉兹博罗夫-鲁迪奇,1994年)以及代数化(阿伦森-维格森,2008年)——表明整整一类已知的证明技术本身都无法解决这一问题,这也是尽管该问题处于核心地位却进展停滞的部分原因。
已知最佳结果
- 目前没有已知的多项式时间算法能解决任何NP完全问题;像3-SAT这样问题的最佳已知算法在最坏情况下仍是指数级的。
- 电路下界仅在受限模型(单调电路、有界深度电路)中得到证明,与分离P和NP所需的一般电路相差甚远。
- 障碍性结果(相对化、自然证明、代数化)表明,整整一类已知的证明技术本身无法单独解决P与NP问题。
使用的方法及其局限
| 方法 | 取得的结果 | 局限所在 |
|---|---|---|
| 对角线法与相对化论证 | 能分离较弱的复杂度类(例如时间层级定理) | 已被证明无法单独解决P与NP问题本身,因为该问题不具有相对化性质(贝克-吉尔-索洛维,1975年) |
| 组合电路下界 | 为单调电路、AC0 等受限电路类证明了指数下界 | 自然证明障碍(拉兹博罗夫-鲁迪奇,1994年)表明,若假设存在强伪随机数生成器,这些技术无法推广到一般电路 |
尚未解决的问题
- P 是否等于 NP?
- 若 P ≠ NP,在 P 与 NP 完全之间是否存在严格中间复杂度的问题(拉德纳定理证明这类问题必然存在,但尚无已知的自然实例)?
参考文献
- Stephen A. Cook (1971). The complexity of theorem-proving procedures
- Richard M. Karp (1972). Reducibility among combinatorial problems
- Stephen Cook (Clay Mathematics Institute) (2000). P vs NP Problem
- Alexander A. Razborov, Steven Rudich (1997). Natural proofs