“P versus NP”（常写作 P vs NP）是计算机科学与复杂性理论中的核心问题：所有能被快速验证答案正确性的难题（NP），是否也都能被快速求解（P）？
通俗说：如果一个问题的解“看一眼就能很快检查对不对”，它是否也一定能“很快找到解”？（这是一个尚未解决的千禧年难题。）
/piː ˈvɜːrsəs ˌɛnˈpiː/
Many people have heard of P versus NP, but few understand why it matters.
很多人听说过 P versus NP，但很少有人明白它为何重要。
If P versus NP were solved with P = NP, many cryptographic systems would become insecure because problems once thought hard could be solved efficiently.
如果 P versus NP 被证明为 P = NP，许多密码系统可能会变得不安全，因为一些原本被认为很难的问题将可以被高效求解。
P 来自 “Polynomial time”（多项式时间），指能在多项式时间内求解的问题集合；NP 常解释为 “Nondeterministic Polynomial time”（非确定性多项式时间），也常被理解为“解可在多项式时间内验证”的问题集合。“versus” 源自拉丁语，意为“对抗/相比”。“P versus NP”这一说法用于概括两类问题集合之间是否相等的争论与研究。
Select Language