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

在非确定多项式(NP)的问题都有些难于理解。在解决NP问题方面，运行时间不能是多项式的。它会像 O(n!) 或更大的东西。

但是，这类问题给出了特定的解决方案，并且检查解决方案将具有多项式运行时间。

例如，数独游戏。

NP 难题

一个问题被称为 NP-Hard，当用于解决 NP Hard 的算法可以转化为解决任何 NP 问题时。那么我们可以说，这个问题至少和任何 NP 问题一样难，但它可能更难或更复杂。

NP-Complete (NPC) 问题是同时存在于 NP 和 NP-Hard 类中的问题。也就是说，NP-Complete 问题可以在多项式时间内得到验证，任何 NP 问题都可以在多项式时间内简化为这个问题。

如果一个问题在 NP 中并且与 NP 中的任何问题一样难，那么它就是 NPC 类。如果 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。