NP-完整VS NP-硬 [英] NP-Complete VS NP-Hard
问题描述
我试图了解NP-Complete和NP-Hard之间的区别。
I am trying to understand the difference between NP-Complete and NP-Hard.
以下是我的理解
一个NP-Hard问题是不能在多项式时间内求解,但可以在多项式时间内验证。
NP完全问题是NP中的一个问题,也是NP-Hard。
An NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time.
An NP-Complete problem is one that is in NP and is also NP-Hard.
以上定义正确吗?如果是这样,那问题不是在NP中而是在NP-Hard中。它们难道不比NP完全问题难,比如只能在指数时间内解决和验证它们吗?
Is the above definition correct? If so, What about problems not In NP but NP-Hard. Wouldn't they be harder than NP-Complete problem, say they can only be solved and verified in exponential time?
推荐答案
一个 NP
问题(不是 NP -Hard
问题)是一个决策问题,可以在多项式时间内进行验证。也许它们可以在多项式时间内解决,因为 P
中的所有问题也都在 NP
中。
A NP
problem (not NP-Hard
problem) is a decision problem which can be verified in polynomial time. Maybe they are solvable in polynomial time, since all problems in P
are also in NP
.
一个 NP完全
问题是一个决策问题,所有 NP
问题可以减少到多项式时间。它们是 NP
类中最困难的问题。
A NP-complete
problem is a decision problem, which all NP
problems can reduced to in polynomial time. They are the hardest problems in the class NP
.
NP困难
类是至少与 NP完全
问题一样困难的问题。它们不一定是决策问题。鉴于我们不知道 NP = P
与否,很难说我们是否可以验证 NP困难
多项式时间内的问题。
The NP-hard
class is the class of the problems which are at least as hard as the NP-complete
problem. They are not necessarily a decision problem. Given that we don't know whether NP = P
or not, it would be hard to say whether we can verify a NP-hard
problem in polynomial time.
例如,最大集团的决策问题(给出图 G
整数 K
,以判断是否存在一个至少具有 K
个顶点的完整图)为 NP
问题。它也是 NP完全
和 NP困难
。但是,最大派系问题(在给定图中找到最大派系)不是 NP
或 NP完全
,因为这不是决策问题。我们可以说这是 NP困难的
,因为它至少与最大集团问题的决策版本一样困难。
For example, the decision problem of maximum clique (Give a graph G
an integer K
, to tell whether there is a complete graph with at least K
vertices ) is NP
problem. It is also NP-complete
and NP-hard
. However, maximum clique problem (Find the maximum clique in the given Graph) is not NP
or NP-complete
, since it is not decision problem. We can say it is NP-hard
, since it is at least as hard as the decision version of maximum clique problem.
这篇关于NP-完整VS NP-硬的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!