我正在尝试理解NP-Complete和NP-Hard之间的区别。
以下是我的理解
NP-Hard问题是指不能在多项式时间内求解,但可以在多项式时间内验证的问题。
NP-Complete问题是指属于NP且也是NP-Hard问题。
上述定义是否正确?如果是这样,那么不在NP中但NP-Hard问题怎么办?它们难道不比NP-Complete问题更难,例如它们只能在指数时间内解决和验证吗?
我正在尝试理解NP-Complete和NP-Hard之间的区别。
以下是我的理解
NP-Hard问题是指不能在多项式时间内求解,但可以在多项式时间内验证的问题。
NP-Complete问题是指属于NP且也是NP-Hard问题。
上述定义是否正确?如果是这样,那么不在NP中但NP-Hard问题怎么办?它们难道不比NP-Complete问题更难,例如它们只能在指数时间内解决和验证吗?
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
,因为它至少与最大团决策问题的难度相同。
如果一个计算问题 p
能够被高效验证,那么它就属于复杂度类 NP。在复杂度理论中,我们认为花费多项式时间的计算是高效的。因此,形式上,当且仅当 p
可以在多项式时间内验证时,p ∈ NP
。
在你的定义中,你提到了多项式时间可解的概念,它对应着复杂度类 P。如果 P = NP,那么 NP-完全问题就是多项式时间可解的。请注意,著名的P vs NP是计算机科学中最大的开放性问题之一,目前没有人知道 P = NP 还是 P ⊊ NP,因此说 NP 问题不是多项式时间可解的是不合适的(尽管广泛相信这是事实)。
从直观上讲,NP-Hard问题是计算问题,其难度至少与NP中的问题一样大。当我们说一个计算问题p
至少与另一个问题q
同样困难时,我们实际上是反过来思考的——如果我们可以在时间T内解决p
,那么我们也可以在大致相同(比如,多项式因子差异)的时间内解决q
。
更确切地说,如果存在多项式时间约化从q
到p
,我们就说p
至少和另一个问题q
一样难。粗略地说,多项式时间约化意味着给定一个解决p
的算法A
,我们可以使用A
作为黑盒(即将A
的时间复杂度视为O(1)
)构建一个多项式时间算法B
来解决q
。
正如您在问题中正确陈述的那样,如果一个计算问题 p
是NP难的并且 p ∈ NP
,那么它就是NP-完全的。
如果存在一个 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,这导致了矛盾!
NP-Hard是问题的下限。不可能的问题也是NP-Hard。NP-Complete意味着它既是NP-Hard,同时也是NP-Solvable。
可以在多项式时间内验证的问题是NP问题的定义之一。