精华内容
下载资源
问答
  • 首先解释一下什么是NP问题,什么是NP hard问题什么是NP完全问题。 看下面的图,他们之间的关系表示的比较清楚。 P Problem:这个应该最易理解,就是一个问题可以在Polynominal的时间的得到解决,当然,是对于任意...

    http://www.cs.pitt.edu/~ztliu/wordpress/2011/05/np-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 http://en.wikipedia.org/wiki/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 http://en.wikipedia.org/wiki/3SAT#3-satisfiability

    举个例子,

    [latex]

    E = (X_1 \lor \lnot X_2 \lor \lnot X_3) \wedge (X_1 \lor X_2 \lor X_4)

    [/latex]

    每一个括号包括的东西叫一个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 http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

    当然这个最显而易见了,就是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是

    [latex]

    E = (X_1 \lor \lnot X_2 \lor \lnot X_3) \wedge (X_1 \lor X_2 \lor X_4)

    [/latex]

    我们按照下面的方法构造我们的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的点相连) (说的好拗口,郁闷。还不清楚的可以看下这个链接http://users.eecs.northwestern.edu/~fortnow/classes/w08/EECS395/lecture11.pdf

    然后,然后,。。。我们就证完了。

    例 用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”的定义了,仁者见仁,智者见智吧。


    先来看一个小故事:(转自:http://zhm2k.blog.163.com/blog/static/5981506820095233143571/

    假如老板要你解决一个问题,你绞尽脑汁还是想不出来,叫天天不应,叫地地不灵,这时你走进老板办公室,可以采取3种策略:

    1)图1:

    一副倒霉像,神情猥琐,可怜巴巴的说:老板,我没做出来,我想我是太蠢了……
    boss:蠢材!滚!
    (失败……)

    2)图2:

    雄赳赳气昂昂跨进老板办公室,大吼一声:小样,你丫给我问题根本就无解,害我白想这么些天,我靠!
    boss:我才靠,自己做不出来就说这个问题无解,要是人人都这样混,我这老板还当个屁阿,滚!
    (做不出来还如此气概,不仅失败,而且欠扁……)

    3)图3:

    从容不迫的说:老板,我做不出来,但是,我敢肯定,那些大牛们也照样做不出来。
    boss:原来是这样,那也难为你了。

     

    以上三副图虽然是一个笑话,但也可以为我们的生活研究提供一些思路和指导。当你面对一个问题解决不了时,那么就试图去证明别人也解决不了,这的确是一个偷懒逃避的好借口。我觉得P、NP、NP-complete、NP-hard这些名称的出现,就是因为某些难问题,连大牛们都解决不了,无可奈何之下,只好定义一堆东西,为自己找个理由,免得说自己太笨了。其实这是给出一个面对难解问题的解决思路,如果无法得到最优解,那么先去尝试验证哪些解是不是最优解。

     

    下面依次介绍

    一、计算复杂性

        计算复杂性一般包括时间复杂度和空间复杂度,时间复杂度并不是某算法实际运行需要的时间,而是渐进时间复杂度,即当问题规模趋向于无穷大时,该算法时间复杂度的数量级。常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。这里用大O表示法来表述,给出的是算法的最坏情况的时间代价。

        复杂度关系:c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!
        其中c是一个常量,如果一个算法的复杂度为c 、 log2N 、n 、 n*log2N ,那么这个算法时间效率比较高,叫做多项式级的复杂度。如果是 2^n , 3^n ,n!,那么稍微大一些的n就会令这个算法不能动了,这些是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

        空间复杂度是指算法在计算机内执行时所需存储空间的度量。这里不再细讲。

        自然地,人们会想到一个问题:会不会所有的问题都可以找到复杂度为多项式级的算法呢?很遗憾,答案是否定的。有些问题甚至根本不可能找到一个正确的算法来,这称之为“不可解问题”(Undecidable Decision Problem)。

    二、P问题(Polynomial Solvable)

    定义:那些可以在多项式( polynomial )时间内解决的问题,称为P问题。(或:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。)

    时间复杂度如(n^2, n^4,  n(log(n)))都是多项式时间的,指数级别的如(2^n,n^n)这些就不是多项式时间了。
    三、NP问题(Non-determinstic Polynomial Solvable)

    定义:给定一个解,我们可以在多项式时间内检查他正确与否的决策问题,为NP问题。
    比如,我要找一个图的哈密顿路径,随便给我一个解,我都可以在多项式时间内检查它是不是哈密顿路径。只要形如定义的问题,就是NP问题。

    之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白,信息学中的号称最困难的问题——“NP问题”,实际上是在探讨NP问题与P类问题的关系。

    很显然,所有的P类问题都是NP问题。也就是说,能多项式地解决一个问题,必然能多项式地验证一个问题的解——既然正解都出来了,验证任意给定的解也只需要比较一下就可以了。关键是,人们想知道,是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中,把所有 NP问题划进另一个集合NP中,那么,显然有P属于NP。现在,所有对NP问题的研究都集中在一个问题上,即究竟是否有P=NP?通常所谓的“NP问题”,其实就一句话:证明或推翻P=NP。

    目前为止这个问题还“啃不动”。但是,一个总的趋势、一个大方向是有的。人们普遍认为,P=NP不成立,也就是说,多数人相信,存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的,就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-complete问题,也即所谓的NPC问题。

    四、归约

    为了说明NPC问题,我们先引入一个概念——约化(Reducibility,有的资料上叫“归约”)。

    简单地说,一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。

    “问题A可约化为问题B”有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。

    从约化的定义中我们看到,一个问题约化为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题,联想起约化的传递性,自然地,我们会想问,如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的 NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC 问题,也就是NP-完全问题。

    五、NP-complete问题

    定义:NP-c问题是这样的一类问题,首先他是属于NP的,而且他是NP问题里面最难解决的问题。难到什么程度?只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。
    既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。因此,给NPC找一个多项式算法太不可思议了。

    “正是NPC问题的存在,使人们相信P≠NP”。我们可以就此直观地理解,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。

    NP-c问题的定义出来了,但是,它忽悠了半天,除了说明这类问题比较难之外,其他啥也没有。我们还是不知道到底什么问题是NP-c问题,如何判定一个问题是不是NP-c问题。
    1970年,cook同志发明了cook定理,找到了第一个NP-c问题,SAT(Satisfiability)问题(逻辑电路问题)。他是这么说的,如果SAT问题可以在P时间解决,那么所有的NP问题都可以在P时间内解决。

    有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题,其他还有图染色问题、背包问题等。现在被证明是NPC问题的有很多,任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说,正是因为NPC问题的存在,P=NP变得难以置信。

    六、NP-hard问题
    定义:NP-hard问题是这样的问题,只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。NP-c问题就是NP-hard问题。但注意NP-hard问题它不一定是NP问题,比如,下围棋就是NP-hard问题,但不是NP问题,我们要在一个残局上找一个必胜下法,告诉我们下一步下在哪里。显然,我们找不这个解,而且更难的是,就算有人给我了一个解,我们也无法在P时间内判断它是不是正确的。

     

    更详细的,以下转自:http://blog.csdn.net/crfoxzl/article/details/2192957

    NP问题就是指其解的正确性可以在多项式时间内被检查的一类问题。比如说数组求和,得到一个解,这个解对不对呢,显然是可以在多项式时间内验证的。再比如说SAT,如果得到一个解,也是能在多项式时间内验证正确性的。所以SAT和求和等等都是NP问题。然后呢,有一部分NP问题的解已经可以在多项式时间内找到,比如数组求和,这部分问题就是NP中比较简单的一部分,被命名为P类问题。那么P以外的NP问题,就是目前还不能够在多项式时间内求解的问题了。会不会将来某一天,有大牛发明了牛算法,把这些问题都在多项式时间内解决呢?也就是说,会不会所有的NP问题,其实都是P类问题呢,只是人类尚未发现呢?NP=P吗?

    可想而知,证明NP=P的路途是艰难的,因为NP问题实在太多了,要一一找到多项式算法。这时Stephen A. Cook这位大牛出现了,写了一篇The Complexity of Theorem Proving Procedures,提出了一个NP-complete的概念。NPC指的是NP问题中最难的一部分问题,所有的NP问题都能在多项式时间内归约到NPC上。所谓归约是指,若A归约到B,B很容易解决,则A很容易解决。显然,如果有任何一道NPC问题在多项式时间内解决了,那么所有的NP问题就都成了P类问题,NP=P就得到证明了,这极大的简化了证明过程。那么怎样证明一个问题C是NP完全问题呢?首先,要证明C是NP问题,也就是C的解的正确性容易验证;然后要证明有一个NP完全问题B,能够在多项式时间内归约到C。这就要求必须先存在至少一个NPC问题。这时Cook大牛就在1971年证明了NP完全问题的祖先就是SAT。SAT问题是指给定一个包含n个布尔变量的逻辑式,问是否存在一个取值组合,使得该式被满足。Cook证明了SAT是一个NPC问题,如果SAT容易解决,那么所有NP都容易解决。Cook是怎样做到的呢?

    他通过非确定性图灵机做到的。非确定性图灵机是一类特殊的图灵机,这种机器很会猜,只要问题有一个解,它就能够在多项式时间内猜到。Cook证明了,SAT总结了该机器在计算过程中必须满足的所有约束条件,任何一个NP问题在这种机器上的计算过程,都可以描述成一个SAT问题。所以,如果你能有一个解决SAT的好算法,你就能够解决非确定性图灵机的计算问题,因为NP问题在非图机上都是多项式解决的,所以你解决了SAT,就能解决所有NP,因此——SAT是一个NP完全问题。感谢Cook,我们已经有了一个NPC问题,剩下的就好办了,用归约来证明就可以了。目前人们已经发现了成千上万的NPC问题,解决一个,NP=P就得证,可以得千年大奖(我认为还能立刻获得图灵奖)。

    那么肯定有人要问了,那么NP之外,还有一些连验证解都不能多项式解决的问题呢。这部分问题,就算是NP=P,都不一定能多项式解决,被命名为NP-hard问题。NP-hard太难了,怎样找到一个完美的女朋友就是NP-hard问题。一个NP-hard问题,可以被一个NP完全问题归约到,也就是说,如果有一个NP-hard得到解决,那么所有NP也就都得到解决了。




    P/NP/NPC/NP-hard概念的图形解释

      开始复习算法,对原来一知半解的基本知识需要慢慢弄懂,其中包括P相关的基本概念(包括P/NP/NPC/NP hard等),从各处看到很多介绍,讲的很多很全面,但都是文字描述,即使耐心看完看懂,但如果长时间不用仍很容易忘记。所以本文用一种图形方法,抽象表达这些概念之间的关系,首先先概要介绍各自概念,然后用图形表示它们之间的关系。

    http://www.cnblogs.com/jpcflyer/archive/2012/04/15/2450622.html

    一、相关概念


         P: 能在多项式时间内解决的问题

      NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决,但能在多项式时间验证的问题

      NPC: NP完全问题,所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题,即解决了此NPC问题,所有NP问题也都得到解决。

      NP hard:NP难问题,所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)。

    二、四者联系的图形表示

      将四种问题用集合表示,它们的关系图1所示。

    图1 P NP NPC NPhard关系的图形表示

     

      说明:

      1. P问题属于NP问题,NPC问题属于NP问题。

      2. NPC问题同时属于NP hard问题,是NP与NPhard的交集。


    展开全文
  • 假如老板要你解决一个问题,你绞尽脑汁还是想不出来,叫天天不应,叫地地不灵,这时你走进老板办公室,可以采取3种策略: 1) 一副倒霉像,神情猥琐,可怜巴巴的说:老板,我没做出来,我想我太蠢了…… boss:...

    先来看一个小故事:(转自:http://zhm2k.blog.163.com/blog/static/5981506820095233143571/

    假如老板要你解决一个问题,你绞尽脑汁还是想不出来,叫天天不应,叫地地不灵,这时你走进老板办公室,可以采取3种策略:

    1)

    一副倒霉像,神情猥琐,可怜巴巴的说:老板,我没做出来,我想我是太蠢了……
    boss:蠢材!滚!
    (失败……)

    2)

    雄赳赳气昂昂跨进老板办公室,大吼一声:小样,你丫给我问题根本就无解,害我白想这么些天,我靠!
    boss:我才靠,自己做不出来就说这个问题无解,要是人人都这样混,我这老板还当个屁阿,滚!
    (做不出来还如此气概,不仅失败,而且欠扁……)

    3)

    从容不迫的说:老板,我做不出来,但是,我敢肯定,那些大牛们也照样做不出来。
    boss:原来是这样,那也难为你了。

    虽然是一个笑话,但也可以为我们的生活研究提供一些思路和指导。当你面对一个问题解决不了时,那么就试图去证明别人也解决不了,这的确是一个偷懒逃避的好借口。我觉得P、NP、NP-complete、NP-hard这些名称的出现,就是因为某些难问题,连大牛们都解决不了,无可奈何之下,只好定义一堆东西,为自己找个理由,免得说自己太笨了。其实这是给出一个面对难解问题的解决思路,如果无法得到最优解,那么先去尝试验证哪些解是不是最优解。

     

    下面依次介绍

    一、计算复杂性

        计算复杂性一般包括时间复杂度和空间复杂度,时间复杂度并不是某算法实际运行需要的时间,而是渐进时间复杂度,即当问题规模趋向于无穷大时,该算法时间复杂度的数量级。常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。这里用大O表示法来表述,给出的是算法的最坏情况的时间代价。

        复杂度关系:c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! 
        其中c是一个常量,如果一个算法的复杂度为c 、 log2N 、n 、 n*log2N ,那么这个算法时间效率比较高,叫做多项式级的复杂度。如果是 2^n , 3^n ,n!,那么稍微大一些的n就会令这个算法不能动了,这些是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

        空间复杂度是指算法在计算机内执行时所需存储空间的度量。这里不再细讲。

        自然地,人们会想到一个问题:会不会所有的问题都可以找到复杂度为多项式级的算法呢?很遗憾,答案是否定的。有些问题甚至根本不可能找到一个正确的算法来,这称之为“不可解问题”(Undecidable Decision Problem)。

    二、P问题(Polynomial Solvable)

        定义:那些可以在多项式( polynomial )时间内解决的问题,称为P问题。(或:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。)

        时间复杂度如(n^2, n^4,  n(log(n)))都是多项式时间的,指数级别的如(2^n,n^n)这些就不是多项式时间了。
    三、NP问题(Non-determinstic Polynomial Solvable)

        定义:给定一个解,我们可以在多项式时间内检查他正确与否的决策问题,为NP问题。
    比如,我要找一个图的哈密顿路径,随便给我一个解,我都可以在多项式时间内检查它是不是哈密顿路径。只要形如定义的问题,就是NP问题。

        之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白,信息学中的号称最困难的问题——“NP问题”,实际上是在探讨NP问题与P类问题的关系。

        很显然,所有的P类问题都是NP问题。也就是说,能多项式地解决一个问题,必然能多项式地验证一个问题的解——既然正解都出来了,验证任意给定的解也只需要比较一下就可以了。关键是,人们想知道,是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中,把所有 NP问题划进另一个集合NP中,那么,显然有P属于NP。现在,所有对NP问题的研究都集中在一个问题上,即究竟是否有P=NP?通常所谓的“NP问题”,其实就一句话:证明或推翻P=NP。

        目前为止这个问题还“啃不动”。但是,一个总的趋势、一个大方向是有的。人们普遍认为,P=NP不成立,也就是说,多数人相信,存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的,就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-complete问题,也即所谓的NPC问题。

    四、归约

        为了说明NPC问题,我们先引入一个概念——约化(Reducibility,有的资料上叫“归约”)。

        简单地说,一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。

        “问题A可约化为问题B”有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。

        从约化的定义中我们看到,一个问题约化为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题,联想起约化的传递性,自然地,我们会想问,如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的 NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC 问题,也就是NP-完全问题。

    五、NP-complete问题

        定义:NP-c问题是这样的一类问题,首先他是属于NP的,而且他是NP问题里面最难解决的问题。难到什么程度?只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。
    既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。因此,给NPC找一个多项式算法太不可思议了。

        “正是NPC问题的存在,使人们相信P≠NP”。我们可以就此直观地理解,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。
        NP-c问题的定义出来了,但是,它忽悠了半天,除了说明这类问题比较难之外,其他啥也没有。我们还是不知道到底什么问题是NP-c问题,如何判定一个问题是不是NP-c问题。
        1970年,cook同志发明了cook定理,找到了第一个NP-c问题,SAT(Satisfiability)问题(逻辑电路问题)。他是这么说的,如果SAT问题可以在P时间解决,那么所有的NP问题都可以在P时间内解决。

        有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题,其他还有图染色问题、背包问题等。现在被证明是NPC问题的有很多,任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说,正是因为NPC问题的存在,P=NP变得难以置信。

    六、NP-hard问题
        定义:NP-hard问题是这样的问题,只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。NP-c问题就是NP-hard问题。但注意NP-hard问题它不一定是NP问题,比如,下围棋就是NP-hard问题,但不是NP问题,我们要在一个残局上找一个必胜下法,告诉我们下一步下在哪里。显然,我们找不这个解,而且更难的是,就算有人给我了一个解,我们也无法在P时间内判断它是不是正确的。

    展开全文
  • 什么是NP问题? 概念1: 在计算机学科中,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题、推销员旅行问题、(命题表达式)可满足问题这类,至今没有找到多项式时间算法解的一类问题,称之为NP类...

     

    什么是NP问题?

    概念1:

    在计算机学科中,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题、推销员旅行问题、(命题表达式)可满足问题这类,至今没有找到多项式时间算法解的一类问题,称之为NP类问题。

    概念2:

    多项式时间(Polynomial time)在计算复杂度理论中,指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类,此类包括可于此机器以多项式时间求解的问题。

    以数学描述的话,则可说m(n) = O(n),此n为一常数值(依问题而定)

    NP问题中最困难的问题称之为NP完全问题(NP-complete),已经证明的包括:电话网络的最优几何设计、格子棋的最佳走法。根据库克定理,任意一个NP完全问题如果能够在多项式时间内解决,则所有的NP问题都能在多项式时间内解决,而至今这一问题仍无答案。

    什么是非确定性问题呢?

    无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间(多项式时间: 运行时间最多是输入量的多项式函数)内算出来,就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。

    完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们於是就猜想,是否这类问题,存在一个确定性算法,可以在指数时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想。

    解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。

    前段时间轰动世界的一个数学成果,是几个印度人提出了一个新算法,可以在多项式时间内,证明某个数是或者不是质数,而在这之前,人们认为质数的证明,是个非多项式问题。可见,有些看来好象是非多项式的问题,其实是多项式问题,只是人们一时还不知道它的多项式解而已。

    什么叫做NP问题,什么叫做NPC问题?

    首先说明一下问题的复杂性和算法的复杂性的区别,下面只考虑时间复杂性。算法的复杂性

    是指解决问题的一个具体的算法的执行时间,这是算法的性质;问题的复杂性是指这个问题本身的复杂程度,是问题的性质。比如对于排序问题,如果我们只能通过元素间的相互比较来确定元素间的相互位置,而没有其他的附加可用信息,则排序问题的复杂性是O(nlgn),但是排序算法有很多,冒泡法是O(n^2),快速排序平均情况下是O(nlgn)等等,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到,一般都是预先估计一个值,然后从理论上证明。

    为了研究问题的复杂性,我们必须将问题抽象,为了简化问题,我们只考虑一类简单的问题,判定性问题,即提出一个问题,只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题,比如求图中从AB的最短路径,可以转化成:从AB是否有长度为1的路径?从AB是否有长度为2的路径?从AB是否有长度为k的路径?如果问到了k的时候回答了yes,则停止发问,我们可以说从AB的最短路径就是k

    如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。

    然而有些问题很难找到多项式时间的算法(或许根本不存在),比如找出无向图中的哈米尔顿回路问题,但是我们发现如果给了我们该问题的一个答案,我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题,给一个任意的回路,我们很容易判断他是否是哈米尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然,所有的P类问题都是属于NP问题的,但是现在的问题是,P是否等于NP?这个问题至今还未解决。

    注意,NP问题不一定都是难解的问题,比如简单的数组排序问题是P类问题,但是P属于NP,所以也是NP问题,你能说他很难解么? 刚才说了,现在还不知道是否有P=NP或者P<>NP,但是后来人们发现还有一系列的特殊NP问题,这类问题的特殊性质使得很多人相信P<>NP,只不过现在还无法证明。这类特殊的NP问题就是NP完全问题(NPC问题,C代表complete)。NPC问题存在着一个令人惊讶的性质,即如果一个NPC问题存在多项式时间的算法,则所有的NP问题都可以在多项式时间内求解,即P=NP成立!!这是因为,每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久,cook1971年找到了第一个NPC问题,此后人们又陆续发现很多NPC问题,现在可能已经有3000多个了。所以,我们一般认为NPC问题是难解的问题,因为他不太可能存在一个多项式时间的算法(如果存在则所有的NP问题都存在多项式时间算法,这太不可思议了,但是也不是不可能)。

    类似哈米尔顿回路/路径问题,货郎担问题,集团问题,最小边覆盖问题(注意和路径覆盖的区别),等等很多问题都是NPC问题,所以都是难解的问题。

     

    NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题).  

    判定方法:

    一个判定性问题,满足:

    (1)∏NP

    (2)对任意一个∏’poly∏ (:poly为规约符号)

    则问题称为NP-完全的(NP-completeNPC);如果问题仅满足条件(2)而不满足条件(1),则问题NP称为NP-难的(NP-hard)

    转载于:https://my.oschina.net/magicalee/blog/699494

    展开全文
  • 你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并...

    什么是P问题、NP问题和NPC问题

    这或许是众多OIer最大的误区之一。
    你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题,什么是NP问题,什么是NPC问题,你如果不是很感兴趣就可以不看了。接下来你可以看到,把NP问题当成是 NPC问题是一个多大的错误。

        还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。不管数据有多大,程序处理花的时间始终是那么多的,我们就说这个程序很好,具有O(1)的时间复杂度,也称常数级复杂度;数据规模变得有多大,花的时间也跟着变得有多长,这个程序的时间复杂度就是O(n),比如找n个数中的最大值;而像冒泡排序、插入排序等,数据扩大2倍,时间变慢4倍的,属于O(n^2)的复杂度。还有一些穷举类的算法,所需时间长度成几何阶数上涨,这就是O(a^n)的指数级复杂度,甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度,因为前面的那个“2”是系数,根本不会影响到整个程序的时间增长。同样地,O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此,我们会说,一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低,尽管在n很小的时候,前者优于后者,但后者时间随数据规模增长得慢,最终O(n^3)的复杂度将远远超过O(n^2)。我们也说,O(n^100)的复杂度小于O(1.01^n)的复杂度。
        容易看出,前面的几类复杂度被分为两种级别,其中后者的复杂度无论如何都远远大于前者:一种是O(1),O(log(n)),O(n^a)等,我们把它叫做多项式级的复杂度,因为它的规模n出现在底数的位置;另一种是O(a^n)和O(n!)型复杂度,它是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

        自然地,人们会想到一个问题:会不会所有的问题都可以找到复杂度为多项式级的算法呢?很遗憾,答案是否定的。有些问题甚至根本不可能找到一个正确的算法来,这称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题,在我的Blog上有过专门的介绍和证明。再比如,输出从1到n这n个数的全排列。不管你用什么方法,你的复杂度都是阶乘级,因为你总得用阶乘级的时间打印出结果来。有人说,这样的“问题”不是一个“正规”的问题,正规的问题是让程序解决一个问题,输出一个“YES”或“NO”(这被称为判定性问题),或者一个什么什么的最优值(这被称为最优化问题)。那么,根据这个定义,我也能举出一个不大可能会有多项式级算法的问题来:Hamilton回路。问题是这样的:给你一个图,问你能否找到一条经过每个顶点一次且恰好一次(不遗漏也不重复)最后又走回来的路(满足这个条件的路径叫做Hamilton回路)。这个问题现在还没有找到多项式级的算法。事实上,这个问题就是我们后面要说的NPC问题。

        下面引入P类问题的概念:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢?通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单,一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。
        接下来引入NP问题的概念。这个就有点难理解了,或者说容易理解错误。在这里强调(回到我竭力想澄清的误区上),NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是,可以在多项式的时间里猜出一个解的问题。比方说,我RP很好,在程序中需要枚举时,我可以一猜一个准。现在某人拿到了一个求最短路径的问题,问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图,但怎么也算不出来,于是来问我:你看怎么选条路走得最少?我说,我RP很好,肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线,说就这条吧。那人按我指的这条把权值加起来一看,嘿,神了,路径长度98,比100小。于是答案出来了,存在比100小的路径。别人会问他这题怎么做出来的,他就可以说,因为我找到了一个比100 小的解。在这个题中,找一个解很困难,但验证一个解很容易。验证一个解只需要O(n)的时间复杂度,也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么,只要我RP好,猜得准,我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的,不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题,即你猜到了解但是没用,因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子,它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然,前面所说的Hamilton回路是NP问题,因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样:试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了,因为除非你试过所有的路,否则你不敢断定它“没有Hamilton回路”。
        之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白,信息学中的号称最困难的问题——“NP问题”,实际上是在探讨NP问题与P类问题的关系。

        很显然,所有的P类问题都是NP问题。也就是说,能多项式地解决一个问题,必然能多项式地验证一个问题的解——既然正解都出来了,验证任意给定的解也只需要比较一下就可以了。关键是,人们想知道,是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中,把所有 NP问题划进另一个集合NP中,那么,显然有P属于NP。现在,所有对NP问题的研究都集中在一个问题上,即究竟是否有P=NP?通常所谓的“NP问题”,其实就一句话:证明或推翻P=NP。
        NP问题一直都是信息学的巅峰。巅峰,意即很引人注目但难以解决。在信息学研究中,这是一个耗费了很多时间和精力也没有解决的终极问
    题,好比物理学中的大统一和数学中的歌德巴赫猜想等。
        目前为止这个问题还“啃不动”。但是,一个总的趋势、一个大方向是有的。人们普遍认为,P=NP不成立,也就是说,多数人相信,存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的,就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题,也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在,使人们相信P≠NP。下文将花大量篇幅介绍NPC问题,你从中可以体会到NPC问题使P=NP变得多么不可思议。

        为了说明NPC问题,我们先引入一个概念——约化(Reducibility,有的资料上叫“归约”)。
        简单地说,一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说,现在有两个问题:求解一个一元一次方程和求解一个一元二次方程。那么我们说,前者可以约化为后者,意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题,那么我们能找到一个“规则”,按照这个规则把解一元一次方程程序的输入数据变一下,用在解一元二次方程的程序上,两个程序总能得到一样的结果。这个规则即是:两个方程的对应项系数不变,一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题,两个问题就等价了。同样地,我们可以说,Hamilton回路可以约化为TSP问题(Travelling Salesman Problem,旅行商问题):在Hamilton回路问题中,两点相连即这两点距离为0,两点不直接相连则令其距离为1,于是问题转化为在TSP问题中,是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。
        “问题A可约化为问题B”有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难,因为解决前者的方法可以用来解决后者。
        很显然,约化具有一项重要的性质:约化具有传递性。如果问题A可约化为问题B,问题B可约化为问题C,则问题A一定可约化为问题C。这个道理非常简单,就不必阐述了。
        现在再来说一下约化的标准概念就不难理解了:如果能找到这样一个变化法则,对任意一个程序A的输入,都能按这个法则变换成程序B的输入,使两程序的输出相同,那么我们说,问题A可约化为问题B。
        当然,我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible),即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

        好了,从约化的定义中我们看到,一个问题约化为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题,联想起约化的传递性,自然地,我们会想问,如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的 NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC 问题,也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信,NPC问题是最复杂的问题。再次回到全文开头,我们可以看到,人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。此时,我的目的终于达到了,我已经把NP问题和NPC问题区别开了。到此为止,本文已经写了近5000字了,我佩服你还能看到这里来,同时也佩服一下自己能写到这里来。

        NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它(由约化的传递性,则NPC问题定义的第二条也得以满足;至于第一个NPC问题是怎么来的,下文将介绍),这样就可以说它是NPC问题了。
        既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。因此,给NPC找一个多项式算法太不可思议了。因此,前文才说,“正是NPC问题的存在,使人们相信P≠NP”。我们可以就此直观地理解,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。

        顺便讲一下NP-Hard问题。NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广)。NP-Hard问题同样难以找到多项式的算法,但它不列入我们的研究范围,因为它不一定是NP问题。即使NPC问题发现了多项式级的算法,NP-Hard问题有可能仍然无法得到多项式级的算法。事实上,由于NP-Hard放宽了限定条件,它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

        不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。
        下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此,逻辑电路问题是NPC类问题的“鼻祖”。
        逻辑电路问题是指的这样一个问题:给定一个逻辑电路,问是否存在一种输入使输出为True。
        什么叫做逻辑电路呢?一个逻辑电路由若干个输入,一个输出,若干“逻辑门”和密密麻麻的线组成。看下面一例,不需要解释你马上就明白了。
      ┌───┐
      │ 输入1├─→┐    ┌──┐
      └───┘    └─→┤    │
                          │ or ├→─┐
      ┌───┐    ┌─→┤    │    │    ┌──┐
      │ 输入2├─→┤    └──┘    └─→┤    │
     &
    nbsp;└───┘    │                ┌─→┤AND ├──→输出
                    └────────┘┌→┤    │
      ┌───┐    ┌──┐            │  └──┘
      │ 输入3├─→┤ NOT├─→────┘
      └───┘    └──┘

        这是个较简单的逻辑电路,当输入1、输入2、输入3分别为True、True、False或False、True、False时,输出为True。
        有输出无论如何都不可能为True的逻辑电路吗?有。下面就是一个简单的例子。
      ┌───┐
      │输入1 ├→─┐    ┌──┐
      └───┘    └─→┤    │
                          │AND ├─→┐
                    ┌─→┤    │    │
                    │    └──┘    │  ┌──┐
                    │                └→┤    │
      ┌───┐    │                    │AND ├─→输出
      │输入2 ├→─┤  ┌──┐      ┌→┤    │
      └───┘    └→┤NOT ├→──┘  └──┘
                        └──┘

        上面这个逻辑电路中,无论输入是什么,输出都是False。我们就说,这个逻辑电路不存在使输出为True的一组输入。
        回到上文,给定一个逻辑电路,问是否存在一种输入使输出为True,这即逻辑电路问题。
        逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题,并且可以直接证明所有的NP问题都可以约化到它(不要以为NP问题有无穷多个将给证明造成不可逾越的困难)。证明过程相当复杂,其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出(想想计算机内部也不过是一些 0和1的运算),因此对于一个NP问题来说,问题转化为了求出满足结果为True的一个输入(即一个可行解)。

        有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题。现在被证明是NPC问题的有很多,任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说,正是因为NPC问题的存在,P=NP变得难以置信。P=NP问题还有许多有趣的东西,有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的,至少是不要把概念弄混淆了。

    展开全文
  • 什么是NP问题 概念1: 在计算机学科中,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题、推销员旅行问题、(命题表达式)可满足问题这类,至今没有找到多项式时间算法解的一类问题,称之为NP类...
  • 什么是NP问题多项式时间现实中的NP类问题 什么是QAP? QAP 是 Quadratic Arithmetic Program 的缩写。 什么是NP问题 【强烈推荐】什么是P=NP问题? 参考URL: https://zhuanlan.zhihu.com/p/143003261 在理解 QAP ...
  • 本文搬运自什么是P问题NP问题和NPC问题,作者是Matrix67,本文在原文之上略做修改,加黑了重点的地方, 对部分稍难理解的地方做了解释,原文已经讲的非常清楚了,向原作者致敬(作者12年前写这篇文章的时候应该...
  • 什么是NP-Hard

    万次阅读 2018-11-19 14:52:28
    所以首先我想解释一下什么是NP-hard问题 在这之前,必须了解一个概念叫做多项式时间:在计算复杂度理论中,指的是一个问题的计算时间不大于问题大小的多项式倍数,通俗些理解我觉得就是一定规模的问题,总有一个...
  • 如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。...NP-Hard问题:所有的NP问题都能规约到它,但它不一定是NP问题。 NP完全问题,也就是多项式复杂程度的非确定性问题.
  • 我也慢慢学习发现到这些问题的趣味,下面我们一起来探讨一下P,NPNP-hardNP-complete这些问题吧!在正式进入之前,先简单列出一波常见的概念。 1.时间复杂度 在遇到算法问题时,就不可避免的需要讨论算法的...
  • 转载自:https://www.matrix67.com/blog/archives/105http://www.coderjie.com/blog/0d2fa4b2693711e8841d00163e0c0e36http://blog.sina.com.cn/s/blog_50c154510100p7zi.html前言:最近做了一个小问题,被老板多次...
  • NP-Hard问题NP-Complete问题的一个直观的理解就是指那些很难(很可能不可能)找到多项式时间算法的问题。因此一般初学算法的人都会问这样一个问题:NP-Hard和NP-Complete有什么不同?简单的回答根据定义,...
  • P问题、NP问题、NPC问题、NP-hard问题详解

    万次阅读 多人点赞 2018-09-19 18:44:24
    要理解P问题、NP问题、NPC问题、NP-hard问题,需要先弄懂几个概念: 什么是多项式时间? 什么是确定性算法?什么是非确定性算法? 什么是规约/约化? 多项式时间(Polynomial time) 什么是时间复杂度? 时间...
  • NP-hard问题:指数级复杂度问题 - 对于小型问题,可以解决 - 采用近似算法解决(可能无法获得精确解) - 指出近似算法 - 指出时间复杂度 - 给出近似算法最后给出的解,离我们想要的最优解有多...
  • 什么说旅行商问题是NP Hard的?网上看了很多文章还是比较迷糊,有谁能清晰地讲解下。怎么样判断一个算法是不是NP Hard
  • NP-Hard问题浅谈

    万次阅读 多人点赞 2016-07-17 23:26:44
    看相关算法的paper的时候,经常会出现NP-Hard这个词。...so,咱们就来看看这个NP-Hard问题,怎么用最简单的方式去了解。1.世界七大数学难题之首2000年,美国克莱数学研究所公布了世界七大数学难题,又称千禧年大
  • P问题是指的存在多项式时间复杂度算法去求解的问题,那么什么是多项式时间复杂度呢? 一个多项式: 我们知道冒泡排序的时间复杂度是O(n^2),这就是一个多项式时间复杂度的算法。 一、P类问题 P问题是指的存在多项式...
  • 总是看到“NP难”或者“NP=P”还有“多项式时间”,这些到底是什么鬼,??今天好好查了一下,按照我自己的理解总结在这里,说实话在这个问题上我感觉百度好像比维基讲得明白些,知乎解释得比百度更清楚…… 下面的...
  • 版权声明:本文为博主原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。 ... 一、p问题、NP问题、NPC问题、NP-hard问题的...1.首先解释一下什么是P问题,什么是NP问题,什么是NPC问题,什么是...
  • 这里梳理下涉及到的知识点,主要参考来源:《什么是P、NP、NPC、NP-Hard问题》、《什么是P问题、NP问题和NPC问题》、《何为NP-hard》、百度百科:NP-hard介绍一些预备知识1. 时间复杂度时间复杂度并不是表示一个程序...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 126
精华内容 50
关键字:

hard问题什么是np