完整VS NP
我想了解NP-Complete和NP-Hard之间的区别。
以下是我的理解
NP-Hard问题是在多项式时间内不可解的问题，但可以在多项式时间内验证。
NP-Complete问题是NP中的问题，也是NP-Hard问题。
上述定义是否正确？ 如果是这样，那么问题不是NP而是NP-Hard。 难道他们不会比NP完全问题更难吗？他们说只能在指数时间内解决和验证它们吗？
一个NP问题（不是NP-Hard难题）是一个可以在多项式时间内验证的决策问题 。 也许它们在多项式时间是可解的，因为P中的所有问题都在NP 。
NP-complete问题是一个决策问题 ，所有NP问题都可以在多项式时间内减少。 它们是NP最难的问题。
NP-hard类是至少与NP-complete问题一样困难的那NP-complete问题。 它们不一定是决策问题。 鉴于我们不知道是否NP = P ，很难说我们是否可以在多项式时间内验证NP-hard难题。
例如，最大团的决策问题（给图G一个整数K ，告诉是否有一个至少具有K个顶点的完整图）是NP问题。 它也是NP-complete和NP-hard 。 然而，最大派系问题（在给定图中找到最大派系）不是NP或NP-complete ，因为它不是决策问题。 我们可以说这是NP-hard ，因为它至少和最大集团问题的决定版一样困难。
NP-Hard是问题的下限。 不可能的问题也是NP-Hard。 NP-Complete意味着它是NP-Hard，同时是NP-Solvable。
可以用多项式时间验证的问题是NP中问题的定义之一。
你对NP-Hard的定义是不正确的，它看起来更像复杂类NP的（不完全正确的）定义。
什么是复杂类NP？
计算问题p在复杂度类NP中，如果它可以被有效地验证。 在复杂性理论中，我们认为使多项式时间有效的计算。 所以正式p ∈ NP如果p是多项式时间验证。
在你的定义中，你提到了概念多项式时间可解，它对应于复杂等级P.当且仅当P = NP时，NP-Complete问题是多项式时间可解的。 请注意，着名的P对NP是计算机科学中最大的开放问题之一，所以目前还没有人知道P = NP还是P⊊NP，并且说NP问题不是多项式时间可解的是不恰当的（尽管它被广泛认为是这种情况）。
什么是NP难题？
直观地说，NP-Hard问题是计算问题，至少与NP中的问题一样困难。 当我们说一个计算问题p至少和另一个问题q一样困难时，我们实际上反过来思考它 - 如果我们可以在时间T上求解p ，那么我们也可以在时间上求解q ，大致与T相同（比如，由多项式因子）。
更确切地说，我们说p至少和另一个问题一样困难q如果从q到p有多项式时间减少。 粗略地说，多项式时间约简意味着给出一个求解p的算法A ，我们可以用A作为黑盒（即我们把A的时间复杂度看作O(1) ）来构造一个多项式时间算法B来求解q 。
在我们的NP-Hard问题的情况下，如果NP-Hard问题可以在多项式时间内解决，那么所有NP问题都可以在多项式时间内求解（因此P = NP！）。 所以普遍认为NP难题不是多项式时间可解的。
NP-Complete问题是什么？
正如你在你的问题中已经正确地陈述的那样，如果它是NP-Hard 且 p ∈ NP ，那么计算问题p是NP-Complete。
不是NP的NP-Hard问题？
如果存在不属于NP的NP-Hard问题（据我所知，此时此刻此类问题没有被证明），这样的问题比NP-Complete问题更难。
证明：假设我们的说法不正确。 设p是一个NP完全问题至少是很难，因为另一个问题q是NP难，但不是在NP。 由于p至少和q一样硬，所以我们有一个从q到p的多项式时间减少（假设它在时间P(n) ）。 由于p在NP中，所以可以通过时间T(n)中的一些算法A来验证，其中T是多项式。
现在给定q任何实例r ，我们可以先构造一个算法B ，先将它缩减为p一个实例s ，然后调用A来验证s 。 注意B验证时间T(P(n)) q ，它是n一个多项式，它遵循q在NP中，这给了我们一个矛盾！
上一篇: Complete VS NP
下一篇: what is the Non