NP,NP-Complete和NP-Hard有什么区别?

but 发布于 2019-11-10 algorithm 最后更新 2019-11-10 12:10 259 浏览

NP,NP-Complete和NP-Hard之间有什么区别? 我意识到网络上的许多资源。我想阅读你的解释,原因是他们可能与那里有什么不同,或者它在外面,我不知道。

已邀请:

non_et

赞同来自:

这个特定的问题有很好的答案,所以没有必要写出我自己的解释。因此,我将尝试为不同类别的计算复杂性提供优质资源。 对于那些认为计算复杂度仅与P和NP有关的人,here is the most exhaustive resource关于不同的计算复杂性问题。除了OP提出的问题之外,它还列出了大约500种不同类型的计算问题,其中包含了很好的描述,还列出了描述该类的基础研究论文。

xet

赞同来自:

据我了解,np-hard问题并不比np-complete问题“难”。实际上,根据定义,每个np完全问题是:

  1. in NP
  2. NP-硬
enter image description here -- Intro. to Algorithms (3ed) by Cormen, Leiserson, Rivest, and Stein, pg 1069

fomnis

赞同来自:

我想我们可以更简洁地回答这个问题。我回答了一个related question,并从那里复制了我的答案 但首先,NP难问题是一个我们无法证明存在多项式时间解的问题。一些“问题-P”的NP-硬度通常通过将已经证实的NP难问题转换为多项式时间中的“问题-P”来证明。

To answer the rest of question, you first need to understand which NP-hard problems are also NP-complete. If an NP-hard problem belongs to set NP, then it is NP-complete. To belong to set NP, a problem needs to be (i) a decision problem,
(ii) the number of solutions to the problem should be finite and each solution should be of polynomial length, and
(iii) given a polynomial length solution, we should be able to say whether the answer to the problem is yes/no Now, it is easy to see that there could be many NP-hard problems that do not belong to set NP and are harder to solve. As an intuitive example, the optimization-version of traveling salesman where we need to find an actual schedule is harder than the decision-version of traveling salesman where we just need to determine whether a schedule with length <= k exists or not.

inemo

赞同来自:

P(多项式时间):正如名称本身所暗示的,这些是可以在多项式时间内解决的问题。 NP(非确定性多项式时间):这些是可以在多项式时间内验证的决策问题。这意味着,如果我声称对于特定问题存在多项式时间解决方案,那么您要求我证明它。然后,我会给你一个证据,你可以在多项式时间内轻松验证。这类问题被称为NP问题。注意,这里我们不讨论是否存在针对该问题的多项式时间解决方案。但我们正在谈论在多项式时间内验证给定问题的解。 NP-Hard:这些至少与NP中最难的问题一样难。如果我们能在多项式时间内解决这些问题,我们就可以解决任何可能存在的NP问题。请注意,这些问题不一定是NP问题。这意味着,我们可能/可能不会在多项式时间内验证这些问题的解决方案。 NP-Complete:这些都是NP和NP-Hard的问题。这意味着,如果我们能够解决这些问题,我们就可以解决任何其他NP问题,并且可以在多项式时间内验证这些问题的解决方案。

xnemo

赞同来自:

解释P v.NP等最简单的方法是将“单词问题”与“多项选择问题”进行比较。 当您尝试解决“单词问题”时,您必须从头开始找到解决方案。 当您尝试解决“多项选择问题”时,您可以选择:或者像解决“单词问题”一样解决问题,或者尝试插入给您的每个答案,然后选择合适的候选答案。 通常情况下,“多项选择问题”比相应的“单词问题”容易得多:替换候选答案并检查它们是否合适可能比从头开始找到正确答案要少得多。 现在,如果我们同意多项式时间“容易”的努力那么P类将由“简单的单词问题”组成,而NP类将由“简单的多选问题”组成。 P v.NP的本质是这样一个问题:“有没有容易的多项选择问题,这些问题不像单词问题那么容易”?也就是说,是否有问题可以很容易地验证给定答案的有效性,但从头开始找到答案很困难? 现在我们直观地理解NP是什么,我们必须挑战我们的直觉。事实证明,存在“多选问题”,从某种意义上说,这些问题最难解决:如果能够找到解决其中“最困难的”问题之一的问题,那么就能找到所有问题的解决方案。 NP问题!当库克在40年前发现这一点时,它完全出乎意料。这些“最困难的”问题被称为NP-hard。如果您找到其中一个“单词问题解决方案”,您会自动为每个“简单的多项选择问题”找到“单词问题解决方案”! 最后,NP完全问题是那些同时NP和NP难的问题。按照我们的比喻,它们同时“容易作为多项选择问题”和“其中最难解决的是单词问题”。

ueum

赞同来自:

NP完全问题是NP-Hard和复杂度NP中的问题。因此,为了表明任何给定的问题是NP完全的,你需要证明问题是在NP中并且它是NP难的。 NP复杂度类中的问题可以在多项式时间中非确定性地求解,并且可以针对多项式时间中的问题验证NP中的问题的可能解(即证书)。 k-clique问题的非确定性解决方案的一个例子是: 1)从图中随机选择k个节点 2)验证这些k个节点形成一个集团。 上述策略是输入图的大小的多项式,因此k-clique问题在NP中。 注意,在多项式时间内确定性地可解决的所有问题也在NP中。 显示问题是NP难的通常涉及使用多项式时间映射从一些其他NP难问题减少到您的问题:http://en.wikipedia.org/wiki/Reduction_(complexity)

comnis

赞同来自:

内容太长未翻译

yhic

赞同来自:

除了其他很好的答案之外,这里还有typical schema用于显示NP,NP-Complete和NP-Hard之间的区别:

enter image description here

rquis

赞同来自:

我一直在环顾四周,看到很多长篇解释。 这是一个小图表,可能有助于总结: 注意难度从上到下增加:任何NP都可以减少到NP-Complete,任何NP-Complete都可以减少到NP-Hard,全部在P(多项式)时间内。 如果你能在P时间内解决一类更难的问题,那就意味着你找到了如何在P时间内解决所有更容易的问题(例如,证明P = NP,如果你弄清楚如何解决任何NP-Complete问题P时间)。

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V
关于YesNo条目的说明:
  • *也是P的NP问题可以在P时间内解决。
  • **同样是NP-Complete的NP-Hard问题在P时间内可以验证。
  • *** NP-完全问题(所有这些都是NP-hard的子集)可能是。 NP的剩余部分不是。
我还发现this diagram非常有用,可以看到所有这些类型如何相互对应(更多地关注图的左半部分)。

jautem

赞同来自:

这是对所提问题的非正式回答。 3233可以写成另外两个大于1的数字的乘积吗?有没有办法绕过所有的Seven Bridges of Königsberg而不需要两次桥接?这些是具有共同特征的问题的示例。如何有效地确定答案可能并不明显,但如果答案是“是”,那么有一个简短快速的检查证据。在第一种情况下,51的非平凡因子分解;在第二个,一个走桥梁的路线(适应约束)。 决策问题是一组问题,其中是或否答案仅在一个参数中有所不同。说问题COMPOSITE = {“是n复合”:n是一个整数}或EULERPATH = {“图表G是否有欧拉路径?”:G是有限图}。 现在,一些决策问题有助于提高效率,即使不是很明显的算法。欧拉在250多年前发现了一种有效的算法来解决诸如“柯尼斯堡的七桥”之类的问题。 另一方面,对于许多决策问题,如何得到答案并不明显 - 但如果你知道一些额外的信息,很明显如何证明你已经得到了正确答案。 COMPOSITE是这样的:试验除法是明显的算法,而且它很慢:要算出一个10位数的数字,你必须尝试类似100,000个可能的除数。但是,例如,如果某人告诉你61是3233的除数,那么简单的长除法是一种有效的方法,可以看出它们是正确的。 复杂性类NP是一类决策问题,其中“是”答案具有简短状态,快速检查证据。像COMPOSITE一样。一个重要的一点是,这个定义并没有说明问题的严重程度。如果您有一个正确,有效的方法来解决决策问题,那么只需写下解决方案中的步骤就足够了。 算法研究仍在继续,并且一直在创建新的聪明算法。你今天可能不知道如何有效解决的问题可能会在明天有一个有效的(如果不是很明显的)解决方案。事实上,研究人员直到2002才能找到COMPOSITE的有效解决方案!随着所有这些进步,人们真的不得不怀疑:这有点短暂的证据只是一种幻觉吗?也许每个有助于高效证明的决策问题都有一个有效的解决方案? Nobody knows。 也许对这一领域的最大贡献来自于发现一种特殊的NP问题。通过利用电路模型进行计算,斯蒂芬库克发现了NP品种的决策问题,这个问题可能比其他NP问题更难或更难。 boolean satisfiability problem的有效解决方案可用于为NP中的任何其他问题创建有效的解决方案。不久之后,理查德卡普表明,其他一些决策问题可以达到同样的目的。从某种意义上说,这些问题是NP中“最难”的问题,被称为NP完全问题。 当然,NP只是一类决策问题。许多问题不是以这种方式自然陈述的:“找到N的因子”,“找到图G中访问每个顶点的最短路径”,“给出一组变量赋值,使得下面的布尔表达式为真”。虽然人们可以非正式地谈论一些这样的问题是“在NP中”,从技术上来说这没有多大意义 - 但它们不是决策问题。其中一些问题甚至可能与NP完全问题具有相同的权力:这些(非决策)问题的有效解决方案将直接导致任何NP问题的有效解决方案。像这样的问题被称为NP-hard。