← 返回单词列表
np-complete
NP-complete 指计算复杂性理论中的“NP完全”的：问题既属于 NP，又至少和 NP 中任何问题一样难。
💡 记忆钩子
把 NP 想成“答案容易核验”的问题集合；NP-complete 问题一方面属于这个集合，另一方面又像一把通用钥匙，NP 中的其他问题都能在多项式时间内转化成它，因此它代表了 NP 问题的共同难点。
📝 学习建议
- 不要把 NP-complete 直接理解成“已经证明无法快速解决”或“所有问题中最难”；它表示在 NP 范围内具有代表性的完整难度，目前通常只知道尚未找到多项式时间算法。
- 先记住它同时包含两个条件：属于 NP，以及是 NP-hard；只满足其中一个条件不能称为 NP-complete。
📖 中文释义
adj
-
core NP完全的📖 指一个问题既属于 NP（给出答案后可以在多项式时间内核验），又是 NP-hard（NP 中的任何问题都能在多项式时间内转化为它）。因此，只要找到一个 NP-complete 问题的多项式时间算法，NP 中所有问题原则上都能这样高效解决。💡 常用模式是“NP-complete problem”或“X is NP-complete”，例如说明某个问题的复杂性类别。它是技术术语，通常不翻成笼统的“非常难的问题”。不要把 NP-complete 和 NP-hard 混用：前者还必须属于 NP，也就是候选答案能在多项式时间内核验。not-comparableThe satisfiability problem is NP-complete.可满足性问题是 NP 完全的。Researchers are studying whether this optimization problem is NP-complete.研究人员正在研究这个优化问题是否属于 NP 完全问题。
🏷 单词标签 & 词根