NP, NP- complete和NP- hard的区别是什么?
我知道网上有很多资源。我想读一下你的解释,原因是它们可能与外界的解释不同,或者有一些我不知道的东西。
NP, NP- complete和NP- hard的区别是什么?
我知道网上有很多资源。我想读一下你的解释,原因是它们可能与外界的解释不同,或者有一些我不知道的东西。
当前回答
找到一些有趣的定义:
其他回答
NP完全问题是那些既NP- hard又属于NP复杂度类的问题。因此,为了证明任何给定的问题是NP完全的,你需要证明这个问题既是NP问题,又是NP难问题。
NP复杂度类的问题可以在多项式时间内非确定性地解决,NP复杂度类问题的可能解(即证书)可以在多项式时间内验证其正确性。
k团问题的非确定性解的一个例子是这样的:
1)从图中随机选择k个节点
2)验证这k个节点组成了一个团。
上述策略在输入图的大小上是多项式,因此k团问题属于NP。
注意,所有在多项式时间内确定可解决的问题也都属于NP。
说明一个问题是np困难的通常包括使用多项式时间映射从其他np困难问题减少到你的问题:http://en.wikipedia.org/wiki/Reduction_(complexity)
解释P和NP的最简单的方法是比较“文字问题”和“多项选择题”。
当你试图解决一个“应用题”时,你必须从头开始寻找解决方案。 当你试图解决一个“多项选择题”时,你有一个选择:要么像解决“应用题”一样解决它,要么试着把给你的每个答案都代入,然后选择一个合适的候选答案。
通常情况下,“多项选择题”比相应的“应用题”容易得多:替换候选答案并检查它们是否合适,可能比从头开始寻找正确答案要省力得多。
现在,如果我们同意花费多项式时间的努力是“简单”的,那么P类将由“简单的应用题”组成,NP类将由“简单的多项选择题”组成。
P和NP的本质是一个问题:“有没有简单的选择题不像应用题那么简单?”也就是说,是否存在这样的问题:验证给定答案的有效性很容易,但从头开始寻找答案却很困难?
现在我们已经直观地理解了NP是什么,我们必须挑战我们的直觉。事实证明,在某种意义上,“多项选择题”是最难的:如果一个人能找到其中一个“最难的”问题的解决方案,那么他就能找到所有NP问题的解决方案!40年前,当库克发现这一点时,完全出乎意料。这些“最难的”问题被称为np难问题。如果你找到其中一个的“应用题解答”,你就会自动找到每一个“简单多项选择题”的“应用题解答”!
最后,NP完全问题是那些同时是NP和NP难的问题。按照我们的类比,它们既“像选择题一样简单”,又“像应用题一样最难”。
P(多项式时间):顾名思义,这些问题可以在多项式时间内解决。
NP (Non-deterministic-polynomial Time):可以在多项式时间内验证的决策问题。这意味着,如果我说有一个多项式时间解对于一个特定的问题,你要我证明它。然后,我会给出一个证明你可以在多项式时间内证明。这类问题被称为NP问题。注意,这里我们讨论的不是这个问题是否存在多项式时间解。但我们讨论的是在多项式时间内验证给定问题的解。
NP- hard:这些问题至少和NP中最难的问题一样难。如果我们能在多项式时间内解决这些问题,我们就能解决任何可能存在的NP问题。请注意,这些问题不一定是NP问题。这意味着,我们可能在多项式时间内验证这些问题的解。
NP完全:这些问题既是NP问题又是NP困难问题。这意味着,如果我们能解决这些问题,我们就能解决任何其他NP问题,这些问题的解可以在多项式时间内得到验证。
根据我的理解,np-hard问题并不比np-complete问题“更难”。事实上,根据定义,每个np完全问题都是:
在NP np-hard
——介绍。Cormen, Leiserson, Rivest, and Stein所著的算法(3ed),第1069页
条件1。和2。翻译成英语:
语言L在NP中,和 每一种NP语言都是多项式时间可约化为语言L。
对于这个特别的问题有很好的答案,所以没有必要写我自己的解释。所以我会试着提供关于不同类型计算复杂度的优秀资源。
对于那些认为计算复杂度只是关于P和NP的人来说,这里有关于不同计算复杂度问题的最详尽的资源。除了OP提出的问题,它还列出了大约500种不同类型的计算问题,并给出了很好的描述,还列出了描述这类问题的基础研究论文。