为什么NP完全问题很重要？

**非确定性多项式 (NP) 问题** 理解起来稍微困难一些。在解决NP问题方面，运行时间不可能是多项式的。它可能是 O(n!) 或更大的东西。

但是，对于这类问题，给定一个特定的解决方案，检查该解决方案将具有多项式运行时间。

例如，数独游戏。

NP难问题

如果一个问题的求解算法可以转化为解决任何NP问题，则称该问题为NP难问题。然后我们可以说，这个问题至少与任何NP问题一样难，但它可能更难或更复杂。

NP完全问题

NP完全 (NPC) 问题是指同时存在于NP和NP难类中的问题。也就是说，NP完全问题可以在多项式时间内验证，并且任何NP问题都可以多项式时间内规约到这个问题。

如果一个问题属于NP类并且与NP类中任何问题一样难，则该问题属于NPC类。如果NP类中的所有问题都可以在多项式时间内规约到它，即使它本身可能不在NP类中，则该问题是NP难问题。

如果对于这些问题中的任何一个存在多项式时间算法，则NP中的所有问题都将可以多项式时间求解。这些问题称为NP完全问题。NP完全现象在理论和实践上都具有重要意义。

NP完全语言很重要

NP完全语言很重要，因为所有NP完全语言都被认为具有相似的难度，因为解决其中一个意味着其他问题也被解决了。

如果一些NP完全语言被证明属于P类，那么所有NP都被证明属于P类。因为，请注意，任何NP语言都可以规约到一个NP完全语言。使用此规约和给定NP完全问题的算法来解决NP中的任何问题。因此，它们都将具有多项式时间解决方案。

如果某个NP完全语言不属于P类，则意味着该语言属于NP类但不属于P类，因此这证明了P类和NP类不相等。

因此，如果某个NP完全问题被证明属于P类或不属于P类，则可以解决P与NP问题。

更新于： 2021年6月14日

1K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习
广告