P 与 NP 问题

定义

P 与 NP 问题是计算复杂性理论中最著名的未解难题。P 类指能在多项式时间内被确定型算法求解的判定问题；NP 类指其解能在多项式时间内被验证的判定问题。该问题询问：凡是解能被快速验证的问题，是否一定也能被快速求解，即 P 是否等于 NP。

原理

显然 P 是 NP 的子集，因为能快速求解必然能快速验证。争论焦点在于反方向是否成立。NP 中存在一类NP 完全问题，如旅行商问题、布尔可满足性问题，它们彼此可在多项式时间内相互归约。只要其中任意一个被找到多项式算法，整个 NP 类便都坍缩进 P。

意义

该问题是克雷数学研究所悬赏百万美元的七大千禧难题之一。若 P 等于 NP，密码学、调度优化、定理证明等领域将发生根本变革；若不相等，则证实许多实际问题本质上难解。绝大多数研究者倾向相信 P 不等于 NP，但至今无人给出严格证明，它仍是理论计算机科学的核心谜题。