NP难和NP完全有什么区别？

如果NP中的每个问题都可以在多项式时间内归约到某个问题，那么该问题就是NP难的，但它本身不一定属于NP，也不一定是判定问题。如果一个问题既是NP难的又属于NP，那么它就是NP完全的。NP完全问题是NP中最困难的问题。

NP完全性是否意味着一个问题永远无法解决？

不是。它意味着对于所有输入，目前没有已知的多项式时间算法，并且如果P不等于NP，则可能不存在这样的算法。在实践中，这类问题通过近似算法、启发式算法、对实际实例有效的指数时间求解器，或通过限制在特殊情况下进行处理。

NP完全性识别出NP类中最困难的问题——那些所有NP问题都可归约到的问题——并为识别那些已知或可能没有高效算法的问题提供了标准框架。

用 PaperMind 寻找选题即将推出Find papers & topics

Tools & resources

Learn & explore

视频即将推出

如果一个判定问题属于NP（其“是”实例具有可有效验证的证书），并且NP中的每个问题都可以在多项式时间内归约到它，那么该问题就是NP完全的；这类问题是NP中最困难的，任何一个问题的多项式时间算法都将为所有问题提供一个算法。

本主题涵盖了复杂性类P和NP、多项式时间归约、NP难和NP完全的定义、确立可满足性为NP完全的库克-莱文定理、卡普的NP完全问题目录，以及难解性对算法设计的实际影响。它将这些概念应用于识别和处理难题；计算复杂性类的更广泛形式理论在计算理论子领域中进行处理。

库克-莱文定理: 库克-莱文定理证明了布尔可满足性（SAT）是NP完全的：NP中的每个问题都可以在多项式时间内归约到它，从而提供了第一个NP完全问题，并为证明其他问题的难度奠定了基础。
组合问题之间的可归约性: 卡普表明，多项式时间归约将许多自然问题——如团问题、顶点覆盖问题、哈密顿回路问题、划分问题等——连接成一个NP完全问题的网络，因此每个问题都可以通过从另一个问题归约来证明其难度。

认识到某个问题是NP完全的，是计算领域中最具实际意义的成果之一：它告诉工程师不要期望找到快速的精确算法，而应转而采用近似算法、启发式算法、针对典型实例优化的精确求解器，或将其限制在可处理的特殊情况。许多调度、路由、打包和设计问题都是NP完全的。

斯蒂芬·库克于1971年引入了NP完全性，证明了SAT是NP完全的；列昂尼德·莱文独立地取得了类似的结果。理查德·卡普1972年的论文展示了21个自然问题是NP完全的，确立了该框架的广泛应用。加里和约翰逊1979年的著作收录了数百个NP完全问题，并成为标准参考。

P对NP: P是否等于NP——即每个可有效验证的问题是否也能有效解决——是该领域最主要的未解决问题；几乎所有研究人员都推测P不等于NP，但该问题尚未解决，并且是千禧年大奖难题之一。

NP难和NP完全有什么区别？: 如果NP中的每个问题都可以在多项式时间内归约到某个问题，那么该问题就是NP难的，但它本身不一定属于NP，也不一定是判定问题。如果一个问题既是NP难的又属于NP，那么它就是NP完全的。NP完全问题是NP中最困难的问题。
NP完全性是否意味着一个问题永远无法解决？: 不是。它意味着对于所有输入，目前没有已知的多项式时间算法，并且如果P不等于NP，则可能不存在这样的算法。在实践中，这类问题通过近似算法、启发式算法、对实际实例有效的指数时间求解器，或通过限制在特殊情况下进行处理。