P-vs-NP
定义 Definition
P vs NP（P 与 NP 之争）是计算机科学中计算复杂性理论的核心问题：
- P：能在“多项式时间”内被算法求解的问题集合。
- NP：给定一个候选答案，能在“多项式时间”内被算法验证的问题集合。
核心疑问是：P 是否等于 NP？（也就是：所有“容易验证”的问题，是否也都“容易求解”？）
注：它也是克雷数学研究所（Clay Mathematics Institute）的千禧年难题之一。
发音 Pronunciation (IPA)
/pi vrz n pi/
例句 Examples
P vs NP is one of the most famous open problems in computer science.
P vs NP 是计算机科学中最著名的未解决问题之一。
If P vs NP were resolved with P = NP, many current cryptographic systems could become insecure, because problems believed to be hard might become efficiently solvable.
如果 P vs NP 被证明为 P = NP，那么许多现有的密码系统可能会变得不安全，因为一些被认为很难的问题可能会变得可以高效求解。
词源 Etymology
“P”来自 Polynomial time（多项式时间）的首字母；“NP”通常解释为 Nondeterministic Polynomial time（非确定性多项式时间）。短语写作 “P vs NP”，其中 “vs” 是 “versus”（对立/比较）的缩写，用来表示两类问题集合之间的关系之争。
相关词 Related Words
文学与名著中的用例 Literary Works
- Michael R. Garey & David S. Johnson, Computers and Intractability（系统讨论 NP 完全性，常提及 P vs NP 背景）
- Michael Sipser, Introduction to the Theory of Computation（复杂性理论经典教材，专章介绍 P、NP 与 P vs NP）
- Stephen Cook (1971), “The Complexity of Theorem-Proving Procedures”（提出 Cook 定理，奠定 P vs NP 讨论基础）
- Richard M. Karp (1972), “Reducibility Among Combinatorial Problems”（提出一批 NP 完全问题，强化 P vs NP 的重要性）
- Clay Mathematics Institute, P versus NP Problem（千禧年难题官方说明文本）
Select Language