猿问
下载APP

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

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

NPNP-CompleteNP-Hard有什么区别?

我知道网上有很多资源。我想阅读你的解释,原因是它们可能与那些不同,或者有些东西我不知道。


BIG阳
浏览 66回答 3
3回答

缥缈止盈

我假设您正在寻找直观的定义,因为技术定义需要相当长的时间才能理解。首先,让我们记住一个初步需要的概念来理解这些定义。决策问题:是或否答案的问题。现在,让我们定义那些复杂性类。PP是一个复杂性类,表示可以在多项式时间内求解的所有决策问题的集合。也就是说,给定问题的实例,可以在多项式时间中确定答案是或否。例给定一个连通图G,它的顶点是否可以使用两种颜色着色,以便没有边是单色的?算法:从任意顶点开始,将其着色为红色,其所有邻居为蓝色并继续。当你用完顶点时停止,或者你被迫使边缘的两个端点都是相同的颜色。NPNP是一个复杂性类,表示所有决策问题的集合,其中答案为“是”的实例具有可在多项式时间内验证的证据。这意味着如果有人向我们提供了问题的实例和证书(有时称为证人),答案是肯定的,我们可以检查它在多项式时间内是否正确。例整数因子分解在NP中。这是给定的整数问题n和m,是否有一个整数f与1 < f < m,使得f分裂n(f是的一小因子n)?这是一个决策问题,因为答案是肯定的或不是。如果有人给我们这个问题的一个实例(所以他们一方面我们整数n和m)和整数f带1 < f < m,并声称f是一个因素n(证书),我们可以检查答案多项式时间内通过执行部门n / f。NP完全NP-Complete是一个复杂性类,它代表XNP&nbsp;中所有问题的集合,Y可以X在多项式时间内将任何其他NP问题减少到NP&nbsp;。直观地说,这意味着Y如果我们知道如何快速解决,我们可以快速解决X。准确地说,Y是还原为X,如果有一个多项式时间算法f改造实例y中Y,以实例x = f(y)的X多项式时间,与答案的性质y是肯定的,当且仅当答案f(y)是肯定的。例3-SAT。这是我们给出3个子句析取(OR)的连接(ANDs)的问题,形式的陈述(x_v11&nbsp;OR&nbsp;x_v21&nbsp;OR&nbsp;x_v31)&nbsp;AND&nbsp;(x_v12&nbsp;OR&nbsp;x_v22&nbsp;OR&nbsp;x_v32)&nbsp;AND&nbsp;...&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AND&nbsp;(x_v1n&nbsp;OR&nbsp;x_v2n&nbsp;OR&nbsp;x_v3n)其中每个x_vij都是布尔变量或来自有限预定义列表的变量的否定(x_1, x_2, ... x_n)。可以证明,每个NP问题都可以减少到3-SAT。这方面的证据是技术性的,需要使用NP的技术定义(基于非确定性图灵机)。这被称为库克定理。NP完全问题的重要之处在于,如果可以找到确定性多项式时间算法来解决其中一个问题,那么每个NP问题都可以在多项式时间内解决(一个问题就是将它们统一起来)。NP难直觉上,这些问题至少与NP完全问题一样困难。请注意,NP难题不必在NP中,并且它们不一定是决策问题。这里的精确定义是,如果存在NP完全问题,则问题X是NP难的Y,这样Y可以X在多项式时间内减少。但由于任何NP完全问题可以在多项式时间内减少到任何其他NP完全问题,所以所有NP完全问题都可以在多项式时间内减少到任何NP难问题。然后,如果在多项式时间内存在一个NP难问题的解,则在多项式时间内存在所有NP问题的解。例该停机问题是一个NP难问题。这是给出程序P和输入的问题,I它会停止吗?这是一个决策问题,但它不在NP中。很明显,任何NP完全问题都可以简化为这个问题。作为另一个例子,任何NP完全问题都是NP难的。我最喜欢的NP完全问题是扫雷问题。P = NP这是计算机科学中最着名的问题,也是数学科学中最重要的突出问题之一。事实上,克莱研究所提供了100万美元用于解决问题的方法(斯蒂芬库克在克莱网站上的写作非常好)。很明显P是NP的子集。悬而未决的问题是NP问题是否具有确定性多项式时间解。人们普遍认为他们没有。这是一篇关于P = NP问题的最新(和重要性)的最新文章:P与NP问题的状态。关于这个主题的最好的书是Garey和Johnson的计算机和难以理解的书。

万千封印

我一直在环顾四周,看到很多长篇解释。这是一个小图表,可能有助于总结:注意难度从上到下增加:任何NP都可以减少到NP-Complete,任何NP-Complete都可以减少到NP-Hard,全部在P(多项式)时间内。如果你能在P时间内解决一个更难的问题,那就意味着你找到了如何在P时间内解决所有更容易的问题(例如,证明P = NP,如果你弄清楚如何解决任何NP-Complete问题P时间)。____________________________________________________________| 问题类型| 可以在P时间内验证 在P时间内可解 增加难度___________________________________________________________ | || P | 是的| 是的| || NP | 是的| 是或否* | || NP-Complete | 是的| 未知| || NP-Hard | 是或否** | 未知*** | |____________________________________________________________ V注释Yes或No条目:*也是P的NP问题在P时间内是可解的。** NP-Hard问题也是NP-Complete在P时间内可以验证。*** NP-Complete问题(所有这些都构成了NP-hard的子集)可能是。NP的其余部分很难。我还发现这个图非常有用,可以看到所有这些类型如何相互对应(更多地关注图的左半部分)。

青春有我

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