在非确定多项式(NP)的问题都有些难于理解。在解决NP问题方面,运行时间不能是多项式的。它会像 O(n!) 或更大的东西。
但是,这类问题给出了特定的解决方案,并且检查解决方案将具有多项式运行时间。
例如,数独游戏。
一个问题被称为 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。