理论与进阶专题
P 与 NP 问题
P 与 NP 问题是计算机科学中最著名的开放问题：核验一个答案，是否本质上和找到它一样容易？P 是我们能快速求解的问题类——多项式时间，意思是运行时间像 n、n^2、n^3 这样增长。NP 是答案可被快速验证的问题类，哪怕找到答案本身可能很难。P 里的每个问题也都在 NP 里（既然能快速解出来，自然也能快速核验）。问题在于反过来是否成立：P 是否等于 NP？
用拼图来体会这个差别。核验一幅拼好的图是否正确很容易——扫一眼就行。而从一堆碎片拼起来则难得多。P = NP 就意味着：归根结底，拼装并不比核验更难——凡是我们能快速辨认出好答案的问题，也存在某种巧妙而快速的办法来构造出一个答案。多数计算机科学家强烈怀疑 P ≠ NP，即确有一些问题在「解」上就是比在「验」上更根本地难，但怀疑不等于证明。
对现状要诚实：这是个未解的问题。没有人证明 P = NP，也没有人证明 P ≠ NP；它是克雷数学研究所那七道百万美元的千禧年大奖难题之一。其分量极其重大。倘若 P = NP，一大批当前棘手的问题——包括那些 NP 完全问题，以及守护现代通信的大量密码学——都将骤然变得可高效求解。倘若 P ≠ NP，我们就得到一个确凿的证明：有些问题天生就难，从而为「退而求其次、采用近似与启发式」这一日常做法提供了正当理由。无论哪个答案都会重塑这个领域；而此刻，诚实的表述只是：我们还不知道。
// P = problems SOLVABLE in polynomial time // NP = problems whose answer is VERIFIABLE in polynomial time // // Known: P is a subset of NP // Unknown: is NP a subset of P ? (i.e. does P = NP ?) // // Status: OPEN. No proof either way exists.
P ⊆ NP 已知；NP 是否 ⊆ P（即 P 是否 = NP）才是悬而未决的问题。
确实未解——千禧年大奖难题之一。多数专家相信 P ≠ NP，但相信不是证明，无论哪个方向的证明都将是里程碑。
又称
另见