P 与 NP 问题（P versus NP）是计算复杂性理论中的核心开放问题. 它询问：如果一个判定问题的候选答案能够被快速验证，这个问题本身是否也一定能够被快速求解.
P 与 NP
P 是能够由确定性算法在多项式时间内求解的判定问题类. NP 是候选解能够在多项式时间内验证的问题类. 因此 P ⊆ NP 已知成立，问题在于 P = NP 是否成立.
NP 完全问题是 NP 中一组具有代表性的最难问题. 如果任何一个 NP 完全问题被证明存在多项式时间算法，就能推出 P = NP；如果证明任何此类算法都不存在，就能推出 P ≠ NP.
为什么重要
这个问题刻画了“找到答案”和“验证答案”之间是否存在根本差异. 它影响算法设计、优化、自动推理和密码学中的许多理论边界，但无论哪种结论都不能简单理解为所有计算任务都会变得容易或困难.
它是千禧年难题之一. 截至 2026 年 9 月，克雷数学研究所仍将其列为未解决问题.