P-vs-NP

定义 Definition

P vs NP（P 与 NP 之争）是计算机科学中计算复杂性理论的核心问题：

• P：能在“多项式时间”内被算法求解的问题集合。
• NP：给定一个候选答案，能在“多项式时间”内被算法验证的问题集合。
  核心疑问是：P 是否等于 NP？（也就是：所有“容易验证”的问题，是否也都“容易求解”？）
  注：它也是克雷数学研究所（Clay Mathematics Institute）的千禧年难题之一。

发音 Pronunciation (IPA)

/ˌpiː vɜːrz ɛ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

• Polynomial-Time
• Nondeterministic
• Complexity
• Reduction
• NP-Complete
• SAT
• Algorithm
• Cryptography

文学与名著中的用例 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（千禧年难题官方说明文本）