NP,NP-Complete和NP-Hard有什么区别？
Dar*_*der 1064 complexity-theory computer-science np-complete np-hard np
NP,NP-Complete和NP-Hard有什么区别？
我知道网上有很多资源.我想阅读你的解释,原因是它们可能与那些不同,或者有些东西我不知道.
jas*_*son 1365
我假设您正在寻找直观的定义,因为技术定义需要相当长的时间才能理解.首先,让我们记住一个初步需要的概念来理解这些定义.
- 决策问题:是或否答案的问题.
现在,让我们定义那些复杂性类.
P
P是一个复杂性类,表示可以在多项式时间内求解的所有决策问题的集合.
也就是说,给定问题的实例,可以在多项式时间中确定答案是或否.
例
给定一个连通图G,它的顶点是否可以使用两种颜色着色,以便没有边是单色的？
算法:从任意顶点开始,将其着色为红色,其所有邻居为蓝色并继续.当你用完顶点时停止,或者你被迫使边缘的两个端点都是相同的颜色.
NP
NP是一个复杂性类,表示所有决策问题的集合,其中答案为"是"的实例具有可在多项式时间内验证的证据.
这意味着如果有人向我们提供了问题的实例和证书(有时称为证人),答案是肯定的,我们可以检查它在多项式时间内是否正确.
例
整数因子分解在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 中所有问题的集合,Y可以X在多项式时间内将任何其他NP问题减少到NP .
直观地说,这意味着Y如果我们知道如何快速解决,我们可以快速解决X.准确地说,Y是还原为X,如果有一个多项式时间算法f改造实例y中Y,以实例x = f(y)的X多项式时间,与答案的性质y是肯定的,当且仅当答案f(y)是肯定的.
例
3-SAT.这是我们给出3个子句析取(OR)的连接(ANDs)的问题,形式的陈述
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR 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的计算机和难以理解的书.
- @Paul Fisher:我将证明SAT可以在多项式时间内减少到停止问题.考虑以下算法:给出作为输入的命令`I` over`n`变量,尝试对变量的所有`2 ^ n`可能的赋值,并且如果一个满足命题则停止,否则进入无限循环.我们看到,当且仅当"I"可满足时,此算法才会停止.因此,如果我们有一个多项式时间算法来解决暂停问题,那么我们可以在多项式时间内解决SAT.因此,停止问题是NP难的. (32认同)
- 使用Halting问题作为NP难问题的"经典例子"是不正确的.这就像是说:"太平洋是盐水水族馆的典型例子." (20认同)
- @Rob:是的,我可以.可还原的定义并不要求将问题简化为可解决的问题.这对于多次减少或图灵减少都是如此. (11认同)
- @Jason - 你不能以这种方式将可判定的问题减少到一个不可判定的问题.可判定的问题必须导致明确的是或否答案才能被认为是可判定的.暂停问题没有确定的肯定或现在的答案,因为任意答案可能会将任何解决方案抛入循环中. (6认同)
- @Rob:好的,好的,如果你想继续这个.首先,"Decidable"与您使用它的"决策问题"并不相关."可判定的"大致意味着有一种"有效的方法"来确定答案.当然,"有效方法"具有技术定义.此外,"可判定的"也可以用"可计算的函数"来定义.因此,暂停问题是一个决策问题("这个程序停止吗？"是一个是/否问题)但它是不可判定的; 没有有效的方法来确定停止问题的实例是否会停止. (5认同)
- @unknown(谷歌):涉及非确定性图灵机的解释是技术上正确的解释.图灵机是我们如何形式化计算机,算法,问题等概念. (3认同)
- @Rob:其次,我认为可还原性的定义并不要求将问题简化为可判定的问题.确切地说,如果给'A`的Oracle算法给'B`,那么我们说'A`是Turing可以简化为'B`.参见,例如,Sipser,计算理论导论. (3认同)
- @Jason 不错的帖子。使用停止问题作为 NP-Hard 问题示例的一个缺点是，它可能会给学生一种（可能是错误的）印象：所有不在 NP 中的问题都是 NP-Hard - 只有当 P 时（对于非平凡问题），这才是正确的= NP。如果 P != NP，则存在不属于 NP 的问题，但这些问题不是 NP 难的。 (3认同)
- @Managu：是的，这就是我说的“NP 难题不一定是 NP 问题”时的意思。我会把这个意思说得更明确。 (2认同)
- @Jason - 抱歉，这是错误的，尽管我必须承认我在声明停止问题没有明确是或否的解决方案时是错误的。这确实是一个决策问题；然而，这是一个无法确定的。您不能以这种方式将 SAT 简化为停机问题的原因是因为停机问题需要提供图灵机 *M* 和输入字符串 *w*，如果 *M* 接受 *w，则它应该接受*，否则拒绝。然而，在通用图灵机上模拟 *M* 可能会导致循环，这就是停机问题不可判定的原因。 (2认同)
- 停机问题的用法是错误的。已经证明没有计算机可以计算停机问题。 (2认同)
Joh*_*ong 247
我一直在环顾四周,看到许多长篇解释.这是一个小图表,可能有助于总结:
注意难度从上到下增加:任何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
注释Yes或No条目:
- *也是P的NP问题在P时间内是可解的.
- **NP-Hard问题也是NP-Complete在P时间内可以验证.
- ***NP-Complete问题(所有这些都构成了NP-hard的子集)可能是.NP的其余部分很难.
我还发现这个图非常有用,可以看到所有这些类型如何相互对应(更多地关注图的左半部分).
- 我对你的回答有疑问。我在一个单独的问题中提出了这个问题，但我被要求将其发布在这里。你能帮我一下吗？http://stackoverflow.com/questions/21005651/how-can-some-np-complete-problems-be-also-np-hard (3认同)
- @FalkHüffner谢谢,表格更新(从维恩图中翻译时出错). (3认同)
Man*_*agu 74
这是对所提问题的非正式回答.
3233可以写成另外两个大于1的数字的乘积吗？有没有办法绕过柯尼斯堡的所有七座桥,而不需要两次搭桥？这些是具有共同特征的问题的示例.如何有效地确定答案可能并不明显,但如果答案为"是",那么有一个简短快速的检查证据.在第一种情况下,51的非平凡因子分解; 在第二个,走桥梁的路线(适应约束).
一个决策问题是有是问题或没有答案,只有在一个参数变化的集合.说问题COMPOSITE = {"Is ncomposite":n是一个整数}或EULERPATH = {"图表是否G有欧拉路径？":G是一个有限图}.
现在,一些决策问题有助于提高效率,即使不是很明显的算法.欧拉在250多年前发现了一种有效的算法来解决诸如"柯尼斯堡的七桥"之类的问题.
另一方面,对于许多决策问题,如何得到答案并不明显 - 但如果你知道一些额外的信息,很明显如何证明你已经得到了正确答案.COMPOSITE是这样的:试验除法是明显的算法,它很慢:要算出一个10位数的数字,你必须尝试类似100,000个可能的除数.但是,例如,如果某人告诉你61是3233的除数,那么简单的长除法是一种有效的方法,可以看出它们是正确的.
复杂性类NP是一类决策问题,其中"是"答案具有简短状态,快速检查证据.像COMPOSITE一样.一个重要的一点是,这个定义并没有说明问题的严重程度.如果您有一个正确,有效的方法来解决决策问题,那么只需写下解决方案中的步骤就足够了.
算法研究仍在继续,并且一直在创建新的聪明算法.你今天可能不知道如何有效解决的问题可能会在明天有一个有效的(如果不是显而易见的)解决方案.事实上,直到2002年,研究人员才找到了有效的COMPOSITE解决方案!随着所有这些进步,人们真的不得不怀疑:这有点短暂的证据只是一种幻觉吗？也许每个有助于高效校对的决策问题都有一个有效的解决方案吗？ 没人知道.
也许对这一领域的最大贡献来自于发现一种特殊的NP问题.通过玩弄电路模型进行计算,斯蒂芬·库克发现的NP品种,这是可证明为硬或比一个更难的问题作出决定每隔其他NP问题.为有效的解决方案布尔可满足性问题可以被用来创建一个有效的解决方案的任何其他在NP问题.不久之后,理查德卡普表明,其他一些决策问题也可以达到同样的目的.从某种意义上说,这些问题是NP中"最难"的问题,被称为NP完全问题.
当然,NP只是一类决策问题.许多问题不是以这种方式自然陈述的:"找到N的因子","找到访问每个顶点的图G中的最短路径","给出一组使下面的布尔表达式为真的变量赋值".虽然可以非正式地谈论一些这样的问题是"在NP中",从技术上说这没有多大意义 - 它们不是决策问题.其中一些问题甚至可能与NP完全问题具有相同的能力:这些(非决策)问题的有效解决方案将直接导致任何NP问题的有效解决方案.像这样的问题被称为NP-hard.
Nag*_*dde 61
P(多项式时间):正如名称本身所暗示的,这些是可以在多项式时间内解决的问题.
NP(非确定性多项式时间):这些是可以在多项式时间内验证的决策问题.这意味着,如果我声称对于特定问题存在多项式时间解决方案,那么您要求我证明它.然后,我会给你一个证据,你可以在多项式时间内轻松验证.这类问题被称为NP问题.注意,这里我们不讨论是否存在针对该问题的多项式时间解决方案.但我们正在讨论在多项式时间内验证给定问题的解.
NP-Hard:这些至少与NP中最难的问题一样难.如果我们能够在多项式时间内解决这些问题,我们就可以解决任何可能存在的NP问题.请注意,这些问题不一定是NP问题.这意味着,我们可能/可能不会在多项式时间内验证这些问题的解决方案.
NP-Complete:这些都是NP和NP-Hard的问题.这意味着,如果我们能够解决这些问题,我们就可以解决任何其他NP问题,并且可以在多项式时间内验证这些问题的解决方案.
- 这个答案比其他答案更好，但我将 NP 解释为“在**非确定性**图灵机上运行时可以在多项式时间内解决的问题”，其中 P 问题是“可以在多项式时间内解决的问题”在**确定性**图灵机上运行时的时间”。这就是 NP 中“非确定性”的真正来源。 (4认同)
- @ArunSatyarth从哪里来？ (2认同)
- 最好的答案很简短，只使用足够的术语，使用普通的人类句子（不难读，让我们尽可能地正确无误），而且令人惊讶的是，唯一的答案写出了N代表什么。 (2认同)
Fra*_*urt 61
除了其他伟大的答案,这里是人们用来显示NP,NP-Complete和NP-Hard之间差异的典型模式:
- @VitorLima是的,例如[EXPSPACE-complete problems](http://en.wikipedia.org/wiki/EXPSPACE)是NP-hard,但证明不是NP-complete. (9认同)
- 是否证明NP-Hard中存在NP-Complete中没有的问题？因为这张图片暗示了它。谢谢你。 (2认同)
- 好的谢谢.我发现了一些关于它的引用.例如,这个:https://www.princeton.edu/~achaney/tmve/wiki100k/docs/NP-hard.html (2认同)
Mic*_*ael 46
解释P v.NP的最简单方法是将"单词问题"与"多项选择问题"进行比较.
当您尝试解决"单词问题"时,您必须从头开始找到解决方案.当您尝试解决"多项选择问题"时,您可以选择:要么像解决"单词问题"一样解决问题,要么尝试插入给您的每个答案,并选择合适的候选答案.
通常情况下,"多项选择问题"比相应的"单词问题"容易得多:替换候选答案并检查它们是否合适可能比从头开始找到正确答案要少得多.
现在,如果我们同意多项式时间"容易"的努力,那么P类将由"简单的单词问题"组成,而NP类将由"简单的多选问题"组成.
P v.NP的本质是这样一个问题:"有没有容易的多项选择问题,这些问题不像单词问题那么容易"？也就是说,是否有问题可以很容易地验证给定答案的有效性,但从头开始找到答案很困难？
现在我们直观地理解NP是什么,我们必须挑战我们的直觉.事实证明,存在"多项选择问题",从某种意义上说,它们中最难的是:如果能够找到解决其中"最困难的"问题之一的问题,那么就能找到所有问题的解决方案. NP问题!当库克在40年前发现这一点时,它完全出乎意料.这些"最困难的"问题被称为NP-hard.如果您找到其中一个"单词问题解决方案",您会自动为每个"简单的多项选择问题"找到"单词问题解决方案"!
最后,NP完全问题是同时NP和NP难的问题.按照我们的比喻,它们同时"容易作为多项选择问题"和"其中最难解决的是单词问题".
Sus*_*rma 18
我想我们可以更简洁地回答这个问题.我回答了一个相关问题,并从那里复制了我的答案
但首先,NP难问题是一个我们无法证明存在多项式时间解的问题.一些"问题-P"的NP-硬度通常通过将已经证明的NP难问题转换为多项式时间中的"问题-P"来证明.
要回答其余问题,首先需要了解哪些NP难题也是NP完全的.如果NP难问题属于集合NP,则它是NP完全的.属于集合NP,需要有一个问题
(i)决策问题,
(ii)问题的解决方案的数量应该是有限的,并且每个解决方案应该是多项式长度,并且
(iii)给定多项式长度解,我们应该能够说出答案是否为问题是是/否现在,很容易看出可能存在许多NP难问题,这些问题不属于集合NP并且难以解决.作为一个直观的例子,我们需要找到实际时间表的旅行推销员的优化版本比旅行推销员的决策版本更难,我们只需要确定长度<= k的时间表是否存在.
awe*_*omo 17
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_(complex)
- 并不是说我在这个答案中看到任何不正确的内容，但我不知道为什么它被接受。它并没有真正满足OP的要求。它与这些问题的标准解释实际上没有什么不同，并且对于这些类中出现这些问题的原因没有任何明确的解释。不值得投反对票，但当然不值得接受答案。 (4认同)