NP-完全与NP-硬

Question

我试图理解NP-完全和NP-Hard之间的区别。

以下是我的理解

NP难问题是在多项式时间内不可解但在多项式时间内可证明的问题。 NP -完全问题是NP中的问题，也是NP-硬问题.

上述定义正确吗？如果是这样的话，那么不是NP的问题，而是NP难的问题。它们难道不比NP-完全问题更困难吗，比如说，它们只能在指数时间内得到解决和验证？

Answer 1

一个NP问题(而不是NP-Hard问题)是一个决策问题，它可以在多项式时间内得到验证。由于P中的所有问题也都在NP中，它们可能在多项式时间内是可解的。

NP-complete问题是一个决策问题，所有的NP问题都可以在多项式时间内归结为NP问题。它们是NP类中最难的问题。

NP-hard类是至少与NP-complete问题一样困难的问题的类。它们不一定是一个决策问题。考虑到我们不知道是否是NP = P，很难判断是否可以在多项式时间内验证NP-hard问题。

例如，最大团的决策问题(给一个图G一个整数K，以判断是否有至少有K顶点的完整图)是NP问题。它也是NP-complete和NP-hard。但是，最大团问题(在给定图中找到最大团)不是NP或NP-complete，因为它不是决策问题。我们可以说它是NP-hard，因为它至少和最大集团问题的决策版本一样困难。

Answer 2

您对NP-Hard的定义是不正确的，它看起来更像是复杂性类NP的定义(不完全正确)。

​

什么是复杂的NP类？

一个计算问题p如果能得到有效的验证，它就属于复杂性类NP。在复杂性理论中，我们认为多项式时间的计算是有效的。因此，形式上是p ∈ NP，如果p是多项式时间可验证的.

在您的定义中，您提到了多项式-时间可解的概念，它对应于复杂性类P。NP -完全问题是多项式-时间可解的当且仅当P=NP。请注意，著名的P对NP是计算机科学中最大的开放问题之一，因此目前还没有人知道P= NP还是P⊊NP，而且说NP问题不是多项式时间可解是不恰当的(尽管人们普遍认为是这样)。

​

什么是NP难题？

从直觉上看，NP困难问题是与NP中的问题一样困难的计算问题。当我们说一个计算问题p至少和另一个问题q一样难的时候，我们实际上会反过来考虑它--如果我们能在时间上求解p，那么我们也可以在时间上求解q --与T大致相同(例如，用多项式因子来表示)。

更准确地说，如果有一个从p到p的多项式时间缩减，那么q至少和另一个问题一样困难。简单地说，多项式时间约简是指给出求解p的算法p，我们可以用A作为黑箱来构造多项式时间算法B (即把A的时间复杂度看作O(1))来求解q。

在我们的NP -硬问题中，如果一个NP-硬问题可以在多项式时间内求解，那么所有的NP问题都可以用多项式时间来解决(因此P= NP!)因此，人们普遍认为NP-硬问题不是多项式-时间可解的.

​

什么是NP-完全问题？

正如你在你的问题中正确指出的，一个计算问题p是NP-完全的，如果它是NP硬和 p ∈ NP。

​

NP -不是NP中的难题吗？

如果在NP中不存在NP困难问题(据我所知，目前还没有证明这类问题属于这一类问题)，那么这样的问题比NP完全问题更困难。

证据:假设我们的说法不正确。设p是一个NP -完全问题，它至少和另一个NP-难的问题一样难，但在NP中不是。由于p至少和q一样难，所以从q到p，我们有一个多项式时间缩减(比如在时间P(n)中运行)。由于p在NP中，它可以通过A在时间T(n)中的某些算法进行验证，其中T是一个多项式。

现在，给定任何实例r of q，我们可以构造一个算法B，首先将其还原为实例s of p，然后调用A来验证s。请注意，B验证了q in time T(P(n))，这是n中的一个多项式，因此q在NP中，这给了我们一个矛盾！

Answer 3

NP-Hard是这个问题的下界.不可能的问题也很难解决。NP-完全表示它是NP-硬的，同时也是NP-可解的.

多项式时间可证明的问题是NP问题的定义之一。