P-Versus-NP

释义 Definition

P versus NP（P 与 NP 之争）是计算机科学（计算复杂性理论）中的一个核心开放问题：所有“容易验证”的问题（NP）是否也都能“容易求解”（P）？
通俗说：如果你能很快检查一个答案对不对，是否就一定也能很快找到这个答案？（目前未知；普遍猜测 P ≠ NP。）

发音 Pronunciation (IPA)

/piː ˈvɜːrsəs ɛn piː/

例句 Examples

Solving Sudoku quickly would be easier if P versus NP were resolved.
如果 P 与 NP 之争得到解决，快速求解数独之类的问题可能会更容易理解其难度本质。

The P versus NP problem shapes how we think about cryptography, because many security systems assume some NP-type problems can’t be solved efficiently.
P 与 NP 问题影响我们对密码学的理解，因为许多安全系统都假设某些 NP 类问题无法被高效求解。

词源 Etymology

该说法来自复杂性理论中的两类问题：P（Polynomial time，多项式时间内可解）与 NP（Nondeterministic Polynomial time，解可在多项式时间内被验证，或等价地：由非确定性图灵机在多项式时间内可解）。
“P versus NP”作为固定表述，常用于指代“P 是否等于 NP”这一著名难题，并与 NP 完全（NP-complete）概念密切相关。

相关词 Related Words

• Complexity
• Algorithm
• Polynomial
• Nondeterministic
• Verification
• Optimization
• Reduction
• NP-Complete
• Cryptography

文学与经典著作 Literary Works

• Stephen Cook, “The Complexity of Theorem-Proving Procedures” (1971)（提出 NP 完全性思想的奠基论文之一）
• Richard M. Karp, “Reducibility Among Combinatorial Problems” (1972)（系统引入并推广 NP 完全问题）
• Michael R. Garey & David S. Johnson, Computers and Intractability (1979)（NP 完全性经典著作）
• Michael Sipser, Introduction to the Theory of Computation（教材中专章讨论 P、NP 与相关问题）
• Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible（面向更广读者讲述 P vs NP 的书）