NP-完整VS NP-硬 [英] NP-Complete VS NP-Hard

查看:247
本文介绍了NP-完整VS NP-硬的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我试图了解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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆