NP问题_百度百科
关闭特色百科用户权威合作手机百科
收藏 查看&NP问题
NP完全(NP Complete,NPC)问题是指这样一类NP问题，所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质：它可以在内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。外文名NP Complete特&&&&点它可以在内求解
首先需要介绍P(Polynomial,多项式)问题.P问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题.NP(Non-Deterministic Polynomial, 非确定多项式)问题,是指可以在多项式时间内被非确定机(他可以猜,他总是能猜到最能满足你需要的那种选择,如果你让他解决n皇后问题,他只要猜n次就能完成----每次都是那么幸运)解决的问题.这里有一个著名的问题----千禧难题之首,是说P问题是否等于NP问题,也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解.
这样一来,只要我们找到一个的多项式解,所有的NP问题都可以多项式时间内划归成这个NPC问题,再用多项式时间解决,这样NP就等于P了.
换一种说法,如果一个问题的是该问题的一个实例规模n的，则这种可以在多项式时间内解决的问题属于P类问题.通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。
有些问题很难找到多项式时间的算法（或许根本不存在），例如“找出无向图中”问题。但如果给了该问题的一个答案，可以在多项式时间内判断这个答案是否正确。例如说对于哈密顿回路问题，给一个任意的回路，很容易判断它是否是哈密顿回路（只要看是不是所有的顶点都在回路中就可以了）。这里给出NP问题的另一个定义,这种可以在多项式时间内验证一个解是否正确的问题称为NP问题，亦称为验证问题类。
简单的说，存在多项式时间的算法的一类问题，称之为P类问题；而像，推销员旅行问题等问题，至今没有找到多项式时间算法解的一类问题，称之为NP问题。同时，P类问题是NP问题的一个子集。1971年，（Stephen A. Cook）发表了 The Complexity of Theorem Proving Procedures（定理证明过程的复杂性）。把以多项式时间解决为衡量标准的问题归成三大类，即NP(nondeterministic poly-nomial)，NP完全(NP-complete)与NP难度问题[1]什么是非确定性（Non-Deterministic）问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在（polynomial）时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。完全多项式非确定性问题可以用得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。
人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
有些看来好像是非的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。
新手上路我有疑问投诉建议参考资料 查看问题的难与易论P,NP及NPC_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
问题的难与易论P,NP及NPC
问​题​的​难​与​易​论​P​,​N​P​及​N​P​C
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢Keywords: NP P NP-hard P NP-complete P P Problem
[为什么写这类文章]&&&
[这系列文章里会用到的一下符号和公式] &&
首先解释一下什么是NP问题，什么是NP hard问题，什么是NP完全问题。
看下面的图，他们之间的关系表示的比较清楚。
P Problem：这个应该最易理解，就是一个问题可以在Polynominal的时间的得到解决，当然，是对于任意input size。
NP Problem：对于一类问题，我们可能没有一个已知的快速的方法得到问题的答案，但是如果给我们一个candidate answer，我们能够在polynominal的时间内验证这个candidate answer到底是不是我们已知问题的答案，这类问题叫做NP problem。所以很显然 P Problem是NP problem的一个子集。
NP-hard Problem：对于这一类问题，用一句话概括他们的特征就是&at least as hard as the hardest problems in NP Problem&， 就是NP-hard问题至少和NP问题一样难。
NP-complete Problem：对于这一类问题，他们满足两个性质，一个就是在polynomial时间内可以验证一个candidate answer是不是真正的解，另一个性质就是我们可以把任何一个NP问题在polynomial的时间内把他的input转化，使之成为一个NP-complete问题。
所以对于NP-hard问题，我们可以把他们分成两个部分，一部分可以用polynomial的时间验证一个candidate answer是不是真正的answer，这一部分问题组成了NP-complete集合。
我们经常说的NP=P或者NP！=P，其实就是说目前而言，我们并不知道，是不是对于NP Problem集合里面的所有问题，都能够在Polynomial的时间内解决。当然只里面比较interesting的一点是，如果我们能把NP-complete集合中的任意一个问题在polynomial的时间内解决了，那么所有的NP问题都可以在polynomial的时间内解决。原因，看看上面说的NP-complete的性质就知道了，因为任何一个NP问题都可以在polynomial的时间内把他的input转化，使之成为一个NP-complete问题，所以....
介绍了上面说的一些定义，来举几个经典的NP-complete的问题。
Vertex Cover&
Informally来说，就是对于一个图G(V,E)，我们在V中选一个subset V'， 使得E中的所有边得两点中的一个点在V'中。 所谓Vertex Cover也就是说V'中的点cover了每一条边（因为每一条边至少有一端是在V'中的啦）给你一个G(V,E)和一个k，问你在整个G中，是否存在一个大小为k的Vertex Cover（Decision Problem）
Formally, a vertex cover of a graph&G&is a set&C&of vertices such that each edge of&G&is incident to at least one vertex in&C. The set&C&is said to&cover&the edges of&G. The following figure shows examples of vertex covers in two graphs (the set&C&is marked with red).
3-CNF-SAT&
举个例子，，每一个括号包括的东西叫一个clause，里面的X1，X2，X3在离散数学里面叫做文字，取值True或者False。每个括号之间是合取，括号里面是析取，这个问题就是，对于这样的一个表达式，是不是能找到一组Xi的值，使得表达式为True。&Given the expression, is there some assignment of&TRUE&and&FALSE&values to the variables that will make the entire expression true?
Integer Linear Programming &
当然这个最显而易见了，就是LP中的所有变量都要求是整数了。关于Linear Programming的问题，后面会专门有一篇文章来讲解。O(&_&)O~
下面来看看我们经常会遇到的一些证明问题。
证明一个问题是NP问题。证明给你一个结果，你能在polynomial的时间内验证他的正确性
证明一个问题是NP-hard的。对于证明一个问题是NP-hard，我们经常用到的一个technique是归约（reduction），通常用&=这个符号来表示，如P&=Q，这个就表示P is reducible to Q or Q is the reduction from P or P is reduced to Q. P问题可以归约到Q问题。可以把P归约到Q。这里的reduction的符号可以当成是 比较难易程度的小于等于号，意味着问题Q至少和问题P一样难。当我们要证明一个问题是NP-hard的时候，我们通常要做的是找到一个NPC问题（就用这个代替NP-complete问题），把这个NPC问题归约到NP-hard上去，即NPC&=NP-hard。
证明一个问题是NPC的。要证NPC，我们要分两步走，第一步证明这个问题属于NP，就是验证答案（感觉这句话我都说烂了）。第二步，证明这个问题是NP-hard的。当然这里面第二步是问题的关键，但是第一步也一定要在证明里面提到。
如何证明一个问题是NP-hard 是以上证明的关键，即如何归约。
这里我们归约要做的主要步骤就是，
1.把NPC的input转化到NP-hard的input，即每一个NPC的input，实际上都是一个NP-hard的input。
2.把NP-hard的output转化到NPC的output上来，说明给我一个NP-hard的output，我就能给你一个NPC的output。
注意：以上的两个转化都要在polynomial的时间内完成。
下面举几个例子来证明上面的归约的方法。
例 用3SAT 证明 Vertex Cover是NP-hard的。即 3SAT &= Vertex Cover
这个就是表明我们已知3SAT这个问题是NP-complete的，如何把3SAT问题归约到Vertex Cover上。
首先，我们要建立我们的通过input建立这两个问题的对应。假设我的3SAT是
我们按照下面的方法构造我们的Graph，对应每一个个变量Xi，我们构造点 Xi和~Xi，对于每一个clause，我们构造3个点，这3个点直接彼此有边，假设这三个点叫A,B,C。同时我们还要建立A,B,C这三个点和该clause的联系：假设我们的clause是 （X1 V ~X2 V ~X3） 我们就把X1和A连起来，~X2和B连起来，~X3和C连起来。注意，每一个clause有一个全连通的三角，他们共用那6个变量点（X1，~X1，X2，~X2，X3，~X3） 如下图所示。
要注意的一点是，对于E中的每一个clause，我们都对应图里面的一个三角形（也就是我用矩形圈住的那部分），同时所有的clause共享上面的六个点，也就是2*变量个数 那么多个点是共用的。
通过这个图，我们也就建立起了3SAT和Vertex Cover之间的联系。通常这个也是此类证明问题中最难和最creative的部分。
后面就是表述一下如何进行转换的。通常这个是很trival的部分。
1）假设我有一个解能满足3SAT，那么我就一定能找到相应的解满足Veterx Cover。 如上图，3SAT满足了，必然每一个clause满足，就拿 (X1 V ~X2 V ~X3) 为例，这个式子满足了，必有一个变量为true，它可以是X1或者~X2或者~X3，假设X1为true，这时对应的vertex cover中，我们就选上面6个点中的X1，同时对于下面的三角形中的3个点，我们选除了那个与X1相连的另外两个点。对于每一个clause，我们都可以这样做，同时，我们也cover了这个图中的所有边。也就是我们有了一个满足要求的vertex cover。
2）假设我有一个解能满足Vertex Cover，那么我就一定能找到相应的解满足3SAT。因为要cover这个图，所以三角形里面至少要cover两个点，上面的一对一对的pair里面也至少要cover一个，所以对于一个size为n+2m的vertex cover（n是变量个数，m是clause的个数），我们一定可以找到一个满足的3SAT，（显然啊，因为每个clause都有一个点和上面的一对一对pair的点相连） （说的好拗口，郁闷。还不清楚的可以看下这个链接 &）
然后，然后，。。。我们就证完了。
例 用3SAT证明ILP是NP-hard的。即 3SAT &= ILP
还是首先找映射，这个映射不涉及图的东西，应该比较容易构造和理解。
还是拿上面那个3SAT的例子说事。对于 每个clause，我们都对应于ILP中的一个constraint，比如 E中有4个变量，X1，X2，X3 和X4， 我们的ILP中也有同样的这4个变量，并且我们要求他们都是只能取0 或 1。对于一个clause，如(X1 V ~X2 V ~X3) ，我们对应的constraint是 &X1 + （1-X2）+（1-X3）&=1&，很显然了，ILP中的变量选0对应于3SAT中的变量选false，ILP中的变量选1对应于3SAT中的变量选true，这样我们就映射好了。
很显然，这两个问题的input/output的转换trival的不行了。如果一个clause满足了，对应的那个ILP中的constraint肯定也满足了；反之依然。偷个懒~O(&_&)O~
这类NP的证明问题其实还是很有难度的，只能说很锻炼脑子，对于它有没有用，这要看你对&useful&的定义了，仁者见仁，智者见智吧。
========================================================================================
本作品采用进行许可。 本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有，欢迎转载，但未经作者同意不得随机删除文章任何内容，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。如您有任何疑问或者授权方面的协商，请给留言。
阅读(...) 评论()NPC问题_百度百科
关闭特色百科用户权威合作手机百科
收藏 查看&NPC问题本词条缺少概述、名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！p问题polynomial problem判定方法一个概&&&&念存在多项式时间的算法的NP问题
在P问题与上的一个重大进展在20世纪70年代初由Cook S和Levin L完成.他们发现NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题).
p问题，可以在多项式时间内解决的问题，polynomial problem。
np 问题，可以在多项式的时间里验证一个解的问题，non-deterministic polynomial
npc问题，如果所有np问题都能在多项式时间内转化为某np问题，则称该np问题为npc问题，np complete
一个，满足：
(2)对任意一个∏’∝poly∏ (注:poly为规约符号)
则问题∏称为NP-完全的(NP-complete，NPC)；如果问题∏仅满足条件(2)而不满足条件(1)，则问题NP称为NP-难的()。
在计算复杂度理论的世界中，NPC问题，又称NP完全问题或NP完备问题，是（非决定性）中最难的。因此NP完备问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合。许多人推测若任何NPC问题得到多项式时间的解法，那此解法就可应用在所有NP问题上。更详细的定义容下叙述。
一个NPC问题的例子是子集合加总问题，题目为
给予一个有限数量的整数集合，找出任何一个此集合的非空子集且此子集内整数和为零。意即：S是一个包括若干整数的集合，找出任一一个S′?S且
这个问题的答案非常容易验证，但目前没有任何一个够快的方法可以在合理的时间内（意即多项式时间）找到答案。只能一个个将它的子集取出来一一测试，它的时间复杂度是Ο（2），n是此集合的元素数量。
假设P ≠ NP的复杂度类的图解。若P =NP则三类别相同。
一个决定性问题C若是为NPC，则代表它对NP是的，这表示：
它是一个NP问题，且
其他属于NP的问题都可归约（reducible）成它。
可归约在此意指对每个问题L，总有一个多项式时间多对一变换，即一个决定性的算法可以将实例l ∈ L 转化成实例c ∈ C，并让c 回答Yes此答案对l 也是Yes。为了证明某个NP问题A实际上是NPC问题，证明者必须找出一个已知的NPC问题可以变换成A。
本定义得到一个结论，就是若上述的C有一个多项式时间可解的算法，则我们可以将所有的NP问题降到P之中。
这个定义是所提出。虽然NPC这个词并没有出现在这篇论文上任何地方。在这个资讯科学会议上，资讯科学家激动地讨论NPC问题是否可以在一个确定型上以多项式时间求解。总结与会众人的共识，认为由于没有人能对某一命题提出驳倒对方的证明，此问题不会于现在解决。此命题就是知名的
P和NP相等吗?。
尚未有人能提出证明，说明NPC问题是否能在多项式时间中解决，使得此问题成为著名的数学中未解决的问题。 位于美国麻省剑桥市的“”（Clay Mathematics Institute，简称CMI）提供了一百万奖金给任何可以证明P=NP或P≠NP的人。
一开始很难相信NPC问题是实际存在的，但著名的古克-李芬定理说明了一切（由Leonid Levin与Cook独立证出SAT问题是NPC问题，简化过但依旧艰深的证明在此）。
在1972年，Richard Karp证明有好几个问题也是NPC（请见卡普的二十一个NP-完全问题），因此除了SAT问题外，的确存在着一整类NPC问题。从古克开始，数千个问题借由从其他NPC问题变换而证实也是NPC问题，其中很多问题被搜集在Garey与于1979年出版的书之中。
满足条件2（无论是否满足条件1）的问题集合被称为。一个NP-hard问题至少跟NPC问题一样难。 有一类问题已经被证明属于NP-hard但不属于NP，即，这类问题至少与NP-complete一样难，但这类问题又不属于NP（自然也不属于NP-complete）。 例如围棋的必胜下法，就是这样一个问题。另一个有趣的例是图同构（isomorphism）问题，即以方法决定两个图是否为同构。两图同构的直觉条件是若其中一图可以经由移动使它与另一个图重合，则为同构。 思考下列两问题：
图同构：图G1是否与图G2同构？
子图同构：图G1是否与图G2的任一子图同构？
子图同构问题是NPC，而图同构问题一般认为不是P也不是NPC问题，虽然它明显是一个NP问题。这是一个典型被认为很难却还不是NPC问题的例子。
想要证明一个问题是NPC，最简单的方法是先证明它属于NP，然后将它变换成某个已知是NPC的问题。因此在学习变换技巧前，先熟悉各种不同类型的NPC问题是很有用的。下表列出了一些以决定性命题表示的著名NPC问题：
布尔可满足性问题：（Boolean satisfiability problem）（SAT）
N-puzzle问题（问题）:（N-puzzle）
：（Knapsack problem）
汉弥尔顿循环问题：（Hamiltonian cycle problem）
：（Traveling salesman problem）
子图同构问题：（Subgraph isomorphism problem）
子集合加总问题：（Subset sum problem）
：（Clique problem）
顶点涵盖问题：（Vertex cover problem）
独立顶点集问题：（Independent set problem）
（参见）:（Graph coloring problem）
更多NPC问题的例子，请见NP-complete问题列表（）。
右边是一些NPC问题及证明其为NPC问题的变换流程图。在流程图中，箭头代表的是从何问题变换成另一问题的过程，要注意的是这张图并不代表这些问题的数学关系，事实上任两个本质为NPC的问题都可以以多项式时间变换，这图仅指示可以让研究者较为简单地变换问题的顺序。
通常一个P与NPC问题的叙述看起来只有一些不同的地方，例如3SAT问题（SAT问题的限制版本）仍然是NPC问题，但更限制的2SAT问题则是个P问题（准确的说，是NL-complete问题），而条件较为宽松的MAX 2SAT问题却又成了NPC问题。决定一个图是否能被两色涂满是P问题，但三色图是NPC问题，即使我们将它限制在上。决定一个图有无循环或它是两分图很容易（在log空间等级），但是发现一个最大二分图或最大循环子图则是NPC。以一固定百分比来求郊游打包问题的最佳解可以在多项式时间解决，但是求最佳解是NPC。目前为止，所有已知解NPC问题的算法需要依照资料数量而定的超多项式（superpolynomial）时间，目前也不知道是否有任何更快的算法存在。因此要在输入资料量大的时候解决一个NPC问题，通常我们使用下列的手段来解：
：这类算法可以快速发现离最佳解在一定差距内的次佳解。
乱数算法：此类算法可提供一乱数产生的输入资料，让本质上解答分布均匀的受测程式可以有良好的求解效率。对于解答分布不均匀的程式，则可以降低乱数程度以改变输入资料。
特例：此算法可以在题目呈献某些特殊情况时快速得解。参数化复杂度（Parameterized complexity）可视为广义的此类算法。
：这种算法在许多时候可以产生理性解答（即运用评比或线索找出解），但无法保证它效率的良莠与解答的好坏程度。
一个启发式算法的例子是用在以O（n log n）的找次佳解，用在某些编译器的暂存器配置阶段上，此技术又叫图着色全域暂存器配置（graph-coloring global register allocation）。每顶点视为一变量，每边代表两变量同时使用的情况，颜色则代表配置给每一变量的编号。由于大多数的RISC机器拥有大量通用暂存器，因此启发式算法很适合用来解这类题目。依照上述NPC的定义，所谓的变换其实是多项式时间多对一变换的简称。
另一种化约法称为多项式时间图灵归约（polynomial-time Turing reduction）。若我们提供一个副函式（subroutine）可以在多项式时间解出&Y&，又可写出呼叫此副函式的程式并在多项式时间解出问题&X&，代表我们可以将&X&多项式时间图灵变换成&Y&。相较起来，不同处在于多对一变换只能呼叫上述副函式一次，且副函式的回传值必须就是整个变换程式回传的值。
如果有人使用图灵变换而非多对一变换来解析NPC，此问题的解答集合不一定会小于NPC。孰大孰小其实是个开放问题。如果两个概念相同，则可导出NP=反NP（co-NP）。此结论成立的道理在于NPC与反NPC的定义以图灵归约来看是相等的，且图灵变换定义的NPC包含多对一变换定义的NPC，反NPC也是相同情况。所以若是两种变换定义的NPC一样大的话，反NPC也会比照办理（在两者的定义之下）。例如SAT的反问题也会是NPC（在两者的定义之下）。因此推得NP = 反NP（证明在反NP条目中）。虽然NP是否等于反NP是个开放问题，但一般认为这似乎不大可能，也因此那两类的NPC定义也不大可能相等。
另一种很常用于NPC证明的变换手法是对数空间多对一变换（logarithmic-space many-one reduction），它是一种可以在对数量级空间运用的多对一变换法。由于每道可以在对数空间完成的运算也可以在多项式时间做完，因此能使用对数空间多对一变换的场合也可以使用多项式时间多对一变换。本方法较多项式时间多对一变换优雅，它也可以让我们对算法复杂度细分出更多分类，例如P完备复杂度。而NPC的定义是否会因为使用不同变换手法而产生差异，仍是一个未知的问题。
新手上路我有疑问投诉建议参考资料 查看图论中P、NP、NPC和NP难问题详解_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
文档贡献者
评价文档：
图论中P、NP、NPC和NP难问题详解
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
大小：1004.50KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢