NP-Complete
定义 Definition
NP-complete（NP 完全）：计算复杂性理论中的一类判定问题。它们满足两点：
- 属于 NP（给出一个“候选解/证书”可以在多项式时间内验证）；
- 是 NP-hard（NP 中任何问题都可以在多项式时间内规约到它）。
因此，NP-complete 常被视为“NP 中最难的一批问题”。（该术语也可引申为“NP 完全的”性质。）
发音 Pronunciation (IPA)
/npi kmplit/
例句 Examples
Many classic scheduling problems are NP-complete.
许多经典的排程问题是 NP 完全的。
Even though a solution can be verified quickly, finding one for an NP-complete problem may take impractically long as the input grows.
尽管解可以很快被验证，但对 NP 完全问题来说，随着输入规模增大，寻找解可能会变得耗时到不切实际。
词源 Etymology
NP 来自 Nondeterministic Polynomial time（非确定性多项式时间），complete 在这里表示“在某个类别中具有代表性的最难问题”。“NP-complete”这一概念在 1970 年代由计算复杂性理论发展起来，用于刻画一批可相互规约、难度等价的核心难题。
相关词 Related Words
文学与经典作品 Literary Works
- Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：系统介绍 NP 完全性与大量典型问题。
- Introduction to the Theory of Computation（Michael Sipser）：以教材形式讲解 NP、NP-complete 与规约。
- Computational Complexity（Christos Papadimitriou）：深入讨论复杂性类与 NP 完全性的理论背景。
- Complexity and Real Computation（Blum, Cucker, Shub, Smale）：在更广义计算模型背景下讨论复杂性概念，涉及相关主题。
Select Language