algorithm - NP-完全 VS NP-困难

Question

我试图了解 NP-Complete 和 NP-Hard 之间的区别。

下面是我的理解

NP-Hard 问题是不能在多项式时间内解决但可以在多项式时间内验证的问题。
NP-Complete 问题是属于 NP 且也是 NP-Hard 的问题。

上面的定义正确吗？如果是这样，那么问题不是在 NP 中而是在 NP-Hard 中。他们不会比 NP-Complete 问题更难，说他们只能在指数时间内解决和验证吗？

Answer 1

NP问题（不是NP-Hard问题）是可以在多项式时间内验证的决策问题。也许它们在多项式时间内是可解的，因为 中的所有问题P也在NP.

NP-complete问题是一个决策问题，所有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

Let me make it simple.

A professor gives his students a problem, and asks them to provide an efficient algorithm.

Next day, some of his intelligent students have cracked the algorithm to solve it. It has a complexity of O(2ⁿ). Now, all are happy that they have got the algorithm to get the solution. Everything looks good.

The professor appreciates them, but says, "The task is not yet over", and challenges them to solve it practically using a system.

So, they immediately try to emulate it in the system. A student says, his system has a fantastic speed of 1 GIPS (1000,000,000 instructions per second) and that it can solve the problem within fractions of a second. So, they code their algorithm and try to execute it.

Then they start with 100 inputs to the data set, and they run it. They were surprised to see that the program runs and runs and runs and doesn't come to a halt.

Then another student did a math on it and figured out that, the system would take 2¹⁰⁰ / 10⁹ seconds to solve it. Roughly around 2⁴⁰ years.

Next day, while the program was still running, the professor said, "Very well. My dear students, this is what we call NP-Hard. The system might give the solution one day, but I'm afraid we won't be there to see it".

But, the same problem, once it generates a solution, if we are able to verify the solution of a NP-Hard problem in realistic time, then it's called NP-Complete. For example, Sum of Subsets is a NP-Hard problem. But, once we get a subset solution, we can check it easily in polynomial time. So it becomes NP-Complete.

Answer 3

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

什么是复杂度类 NP？

p如果可以有效地验证计算问题，则它属于复杂度类 NP 。在复杂性理论中，我们认为需要多项式时间的计算是有效的。所以形式上p ∈ NPif pis polynomial-time verifiable。

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

什么是 NP-Hard 问题？

直观地说，NP-Hard 问题是至少与NP 中的问题一样难的计算问题。当我们说一个计算问题p至少和另一个问题一样难时q，我们实际上是反过来想的——如果我们可以p在时间 T内解决，那么我们也可以在与 T大致相同q的时间内解决（例如，相差一个多项式因子）。

更准确地说，如果多项式时间从到，我们说这p至少和另一个问题一样难。粗略地说，多项式时间约简是指给定一个求解 的算法，我们可以构造一个多项式时间算法，使用as 黑盒（即我们将时间复杂度视为）来求解。qqpApBAAO(1)q

在我们的 NP-Hard 问题中，如果 NP-Hard 问题可以在多项式时间内解决，那么所有NP 问题都可以在多项式时间内解决（因此 P = NP！）。因此，人们普遍认为NP-hard 问题不是多项式时间可解的。

什么是 NP 完全问题？

正如您在问题中正确陈述的那样，如果计算问题p是 NP-Hard并且 p ∈ NP.

不属于 NP 的 NP-Hard 问题？

如果存在不属于 NP 的 NP-Hard 问题（据我所知，目前还没有证明此类问题属于此类），则此类问题比 NP-Complete 问题更难。

证明：假设我们的主张不正确。让p是一个 NP-Complete 问题，它至少与另一个qNP-Hard 但不是 NP 的问题一样难。因为p至少和 一样难q，所以我们有一个多项式时间缩减（比如它在时间 中运行P(n)）从q到p。由于p在 NP 中，因此可以通过一些算法A及时验证T(n)其中T是多项式。

现在给定 的任何实例r，我们可以通过首先将其简化为 的实例，然后调用来验证q来构造一个算法。请注意，在 time中验证，它是 中的多项式，因此在 NP 中，这给了我们一个矛盾！BspAsBqT(P(n))nq

Answer 4

NP-Hard 是问题的下界。不可能的问题也是 NP-Hard。NP-Complete 意味着它是 NP-Hard 并且同时是 NP-Solvable。

可以在多项式时间内验证的问题是NP中问题的定义之一。

Answer 5

您的定义仅对 NP 完全正确。

从底部开始：P 是可以由某些确定性图灵机在多项式时间内解决的一类问题。NP是可以在多项式时间内由某些非确定性图灵机解决的问题类别（或者其解决方案可以在多项式时间内由确定性图灵机验证）。

至于 NP-hard，它意味着具有以下性质的决策问题 X：给定解决问题的图灵机，可以在多项式时间内将 NP 中的任何问题实例重构（图灵约简）为 X 的实例。非正式地，这意味着 NP-hard 问题是“至少与 NP 一样难”的问题，或者 X 的解决方案可以应用于 NP 中的每个问题。请注意，问题不必在多项式时间内是可验证的，或者实际上是可验证的。NP-hard 也包括不可判定和不可识别的问题。

我们不知道 NP-hard 是否包括可以在多项式时间内解决的问题（P ?= NP 问题）。目前，还没有找到单一的多项式时间解决 NP-hard 问题，但也没有证明这样的解决方案不存在。如果为某些 NP-hard 问题 X 找到了这样的解决方案，那将意味着 P = NP，因为 NP 中的任何问题的任何实例都可以在多项式时间内转换为 X 的实例（因为 NP-hard 的图灵简化特性问题），然后通过 X 的多项式时间解在多项式时间内求解。