我正在尝试理解NP-Complete和NP-Hard之间的区别。
以下是我的理解
NP-Hard问题是指不能在多项式时间内求解，但可以在多项式时间内验证的问题。
NP-Complete问题是指属于NP且也是NP-Hard问题。
上述定义是否正确？如果是这样，那么不在NP中但NP-Hard问题怎么办？它们难道不比NP-Complete问题更难，例如它们只能在指数时间内解决和验证吗？
NP-Complete与NP-Hard的区别
12
- ade19
1
2目前尚不清楚（并且价值100万美元），NP完全问题是否可以在多项式时间内解决。 - Rob Neuhaus
5个回答
28
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，因为它至少与最大团决策问题的难度相同。
- notbad
9
让我来简单解释一下。一位教授给他的学生出了一道问题，并要求他们提供一个高效的算法。第二天，一些聪明的学生已经破解了解决它的算法。它的复杂度为 O(2^n)。现在，所有人都很高兴地发现，他们已经得到了解决方案的算法。看起来一切都很顺利。教授对他们表示赞赏，但说：“任务还没有完成”，并向他们提出挑战，要求他们使用系统实际解决这个问题。因此，他们立即尝试在系统中模拟它。一位学生说，他的系统拥有1 GIPS（每秒100亿次指令）的惊人速度，可以在几分之一秒内解决问题。因此，他们编写自己的算法并尝试执行它。然后，他们从数据集中输入100个数据进行测试，并运行程序。他们惊讶地发现，程序一直运行而且不停止。然后另一个学生对此进行了计算，并计算出该系统需要 2^100 / 10^9 秒才能解决它。大约需要2^40年。第二天，当程序仍在运行时，教授说：“非常好，亲爱的学生们，这就是我们称之为NP-Hard的问题。该系统可能有一天会给出解决方案，但恐怕我们不会在那里看到它。”但是，同样的问题一旦生成解决方案，如果我们能够在实际时间内验证NP-Hard问题的解决方案，那么它被称为NP-Complete问题。例如，“子集和”是一个NP-Hard问题。但是，一旦我们得到了一个子集解决方案，我们可以很容易地在多项式时间内进行检查。因此它变成了NP-Complete。
- Vishnu Vivek
1
1谢谢！想要这样简单的解释！！ - Shivansh Jagga
3
你对NP-Hard的定义不正确，看起来更像是复杂度类NP的（不是非常准确的）定义。
什么是复杂度类 NP？
如果一个计算问题 p 能够被高效验证，那么它就属于复杂度类 NP。在复杂度理论中，我们认为花费多项式时间的计算是高效的。因此，形式上，当且仅当 p 可以在多项式时间内验证时，p ∈ NP。
在你的定义中，你提到了多项式时间可解的概念，它对应着复杂度类 P。如果 P = NP，那么 NP-完全问题就是多项式时间可解的。请注意，著名的P vs NP是计算机科学中最大的开放性问题之一，目前没有人知道 P = NP 还是 P ⊊ NP，因此说 NP 问题不是多项式时间可解的是不合适的（尽管广泛相信这是事实）。
什么是NP-Hard问题？
从直观上讲，NP-Hard问题是计算问题，其难度至少与NP中的问题一样大。当我们说一个计算问题p至少与另一个问题q同样困难时，我们实际上是反过来思考的——如果我们可以在时间T内解决p，那么我们也可以在大致相同（比如，多项式因子差异）的时间内解决q。
更确切地说，如果存在多项式时间约化从q到p，我们就说p至少和另一个问题q一样难。粗略地说，多项式时间约化意味着给定一个解决p的算法A，我们可以使用A作为黑盒（即将A的时间复杂度视为O(1)）构建一个多项式时间算法B来解决q。
什么是NP-完全问题？
正如您在问题中正确陈述的那样，如果一个计算问题 p 是NP难的并且 p ∈ NP，那么它就是NP-完全的。
不在 NP 中的 NP-Hard 问题?
如果存在一个 NP-Hard 问题不属于 NP （就我所知，目前没有证明有这种问题），那么这个问题比 NP-Complete 问题更难。
证明： 假设我们的说法不成立。让 p 是一 NP-Complete 问题，它至少和另一个 NP-Hard 但不属于 NP 的问题 q 一样难。由于 p 至少和 q 一样难，我们有一个多项式时间约简（假设它运行在时间 P(n) 内）从 q 到 p。由于 p 属于 NP，它可以通过某个算法 A 在时间 T(n) 内验证，其中 T 是一个多项式。
现在，对于任何q的实例r，我们可以通过先将其归约为p的实例s，然后调用A来验证s，从而构建一个算法B。请注意，B在n的多项式时间T(P(n))内验证q，因此，q属于NP，这导致了矛盾！
- chiwangc
2
NP-Hard是问题的下限。不可能的问题也是NP-Hard。NP-Complete意味着它既是NP-Hard，同时也是NP-Solvable。
可以在多项式时间内验证的问题是NP问题的定义之一。
- Kuba
1
你并没有解释NP-hard是什么，但是你又将NPC定义为NP-hard和NP的交集？这里肯定有些东西缺失了。 - Niklas B.
2
你的定义只适用于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-hard问题的图灵约减属性，将NP中的任何问题的实例转换为X的实例，并通过X的多项式时间解法在多项式时间内解决。
从最基本的开始：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-hard问题的图灵约减属性，将NP中的任何问题的实例转换为X的实例，并通过X的多项式时间解法在多项式时间内解决。
- kviiri
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接