什么是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问题还有许多有趣的东西,有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的,至少是不要把概念弄混淆了。

Matrix67原创
转载请注明出处

196 条评论

  • 那么那么地

    牛啊,博主不是一般的牛
    能把比较复杂的东西表达的非常清晰非常条理,真不简单

  • 懒羊羊

    感谢楼主,总算明白这三个东西了

  • guest

    很牛的楼主,可以将问题表述的如此有条理和清晰;坚持不懈,中国将出现另外一个大家,建议学习“自然语言处理”(AI范畴):)

  • AIP

    Just 2 questions:
    Does NP stand for Not-Polynomial?
    What does OI mean?

    http://isdox.com

    回复:Non-deterministic Polynomial
    Olympiad in Informatics

  • ---

    老哥你是干啥的啊。。。真佩服你在这么浮躁的年代还能耐的住来研究这些。

  • Alexandra

    这句话:
    再证明其中一个已知的NPC问题能约化到它.

    应该是:
    再证明其中一个已知的NP问题能约化到它吧?

    回复:没写错,如果一个问题可以由某个npc问题归约得到,则所有的np问题都能归约到它

  • dahe_1984

    厉害!

    受益匪浅!  '匪'是贬义,这个词是褒义.是否存在一定的条件转换把贬义的字变成褒义词呢?.

  • Clude

    我也文科的呀!
    QQ121195036
    Noip C语言提高组. 15353287(我的群)
    请大家帮忙宣传!

  • wiwo

    看完了,感觉豁然开朗

  • wiwo

    我想看看地核下面是什么

  • alexmajy

    恩,这是我迄今看到得讲的最清楚的的一篇文章啦

  • is

    到此一游

  • 崇拜

    支持!很清晰,没啥可说的了,我尽量把大牛写的每篇文章理解一下。

  • luck

    牛人,支持。偶然的机会到了你的博客,看了几篇文章(主要是计算机的),感觉真的是一篇比一篇好。
    能加一下我的qq吗?以后有什么问题就能请教你了,呵呵
    QQ:379004115

  • Megdeath

    写的非常好 哲人的思考 常人的表达

  • bored-by-hamilton

    很有趣。

  • crg511

    佩服~今晚再细看一遍。大牛,您辛苦了,为人民服务啊。

  • www

    牛,太牛了,终于搞明白了

  • Gavin

    牛,之前我做过一些启发是算法的问题,现在看这个无疑是总结性的提高。太牛了

  • 笨笨de砖

    细看一遍后,豁然开朗。。。

  • czz

    强!很强!十分强!

  • yaoyao

    NP问题的另一个定义是,可以在多项式的时间里猜出一个解的问题。
    那么有什么问题是一次猜不中而需要多项式时间才能猜中的?

  • kui

    这个结果于2000年发表在Mathematical Intelligencer上,论文题目是Minesweeper is NP-complete,
    link:http://blog.csdn.net/leetonven/archive/2008/11/14/3297520.aspx

  • CAI

    谢谢了,讲得很清楚

  • tinza

    佩服 虽然很长 但是说的很清楚

  • biohu

    回11楼,我总结了一个 热力学第四定律:
    解决NPC问题导致的熵的增加>P
    (ps:前面几个分别为
    零:AB热平衡且BC热平衡,则AC热平衡。一:能量守恒。二:熵增。三:达不到绝对零度。)

  • arena_zp

    受用了 :-)
    写作思路很清晰

  • 骑龙的傻瓜

    NP问题是否能在多项式时间内求解呢??

    • ika

      NP问题集包括了P和NPC,所以如果P≠NP,依然有一部分NP问题可以在多项式时间内求解。

  • 张若寒

    同行,和你一样喜欢研究别人不研究的东西,加个好友吧我QQ1025679612

  • netplanetde

    挺相信NP不等于P的,否则怎么会那么巧上百个NPC问题都没有任何一个被找到有多项式算法。。。

  • K2

    请问这是哪个学科的?我怎么完全看不懂?
    但我很感兴趣

  • aniquier

    大牛啊
    写的清晰易懂,可见博主的内功是何等之深厚
    收藏了,谢谢

  • Actor

    真是功底雄厚!无比崇拜!

  • lzb198259

    透彻,太有水平了。

  • lzb198259

    不过要是能把规约化的方法也大致介绍一下就好了

  • xuehui869

    据说被惠普的一个研究员证明了。这两天还在看这个命题,没想到今天上午就看到了被证明P!=NP 。。。

  • wildmagic

    博主太強了。。。求邏輯電路NPC證明的資料

  • CuI

    3楼的大牛……
    于是你四年前的日志在今天成功的成为了很及时的重要科普……

  • zhaiduo

    晕啊,看不懂

  • Daniel

    攀登这个信息学的巅峰是我们这一代的终极目标。

  • Gameboy

    大哥你写的太棒了,膜拜!!太棒了

  • zh

    我们教授级的老师都没讲清楚的问题,你居然能这么有条理易懂的把它讲完,佩服佩服

  • Hengfeng Li

    实在是不得不回一下帖。。。
    高三就懂这些了,实在很佩服,而且讲的这么清楚。。。
    作为同龄人,实在很惭愧。。。

  • Lee

    楼主很牛!佩服佩服

  • John

    楼主帮了大忙

  • camper

    NPC问题在时间复杂度上是否还有区别呢?所有的NPC都假定时间复杂度相同吗?

    • ika

      可以这么理解,因为所以NPC问题都可以互相归约,既时间复杂度难度相等

  • Marvin Lynx

    兄弟,字体有点小。

  • Bitex

    现任oier努力学习

  • wallson

    果然是大牛啊,说理透彻,深入浅出,佩服佩服

  • dlad

    深入浅出
    算法导论若能由lz润色下就好了

  • 爱之风情

    膜拜。。。。。。

  • ET民工[源自火星]

    “O(n^100)的复杂度小于O(1.01^n)的复杂度”——这个有没有写反啊?前者的增长速度要比后者快吧

  • ed

    相互抄袭

  • mil64

    关于约化我可不可以这么理解
    电路1 有三个输入
    电路2 也有三个输入

    对于使电路1输出为true的所有输入 电路2同样也输出true
    并且也存在其他的输入使得电路2输出为true

    那么电路2是电路1的一个约化

    是这样理解么?

  • easoncxz

    发现沙发竟然是文章出现一年之后的事!看来就是这一年里,博客成长了不少,招来不少读者啊。

  • cong

    我最近遇到一个寻找Hamilton回路的问题,图已经确定是一个完全三分图K3(5),就是分三组,每组5个顶点的。要回答两个问题,首先是要判断该图是否存在两条没有重叠边的Hamilton回路,然后把所有Hamilton回路找出来。
    有什么好的建议吗?

  • 飘林迷丁儿

    Leonard M. Adleman话说这么个人提出了DNA computing,也许可以给H回路找到多项式级算法

  • 狮子

    太牛逼了,偶然搜到这篇文章,佩服至极。

  • csyaonie

    第一次看到这么牛逼的文章 像是中科院的牛人
    不得不顶一下

  • sdx

    谢谢博住,明天考试就考这个。:-)转走了

  • 菜籽

    是不是说所有的NPC问题都可以互相约化?或者说是不是解决了一个NPC问题就相当于解决了所有的NPC问题?

  • 加贝

    大神,拜读了你这篇文章之后把NP,NPC这些概念一下子都弄懂了!!!感谢

  • inph

    算法考试有底了

  • zausiu

    大牛啊~~膜拜啊~~~~

  • xiaoxingxing

  • 猫牛

    很多人讲这个都是抄来的可能他们自己都不懂的废话 只有楼主讲的深入浅出的非常清晰,我觉得能讲清楚的人才是明白人

  • jackqdyulei

    原文中有几处不是很理解,望赐教。
    1. “现在某人拿到了一个求最短路径的问题,问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图,但怎么也算不出来,于是来问我:你看怎么选条路走得最少?我说,我RP很好,肯定能随便给你指条很短的路出来。”。那如果这个问题本身就没有小于100的路线,自然也就选不出来,那样岂不就不是NP问题了?
    2.“但我要把问题换成这样:试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了,因为除非你试过所有的路,否则你不敢断定它“没有Hamilton回路”。”在这个问题中,我也可以假设我的RP非常好,一下子找到了一条Hamilton回路并验证了它,那这样问题岂不迎刃而解了?因为“图中存在一条Hamilton回路”。

    • 河童

      今天还有人回复,握手,可不可以讨论下NP问题的定义,博主写的是可以在多项式时间内验证一个解与可以在多项式的时间里猜出一个解的问题。这里的验证是说,我随便给一个解,只要在多项式时间内验证它正确与否还是说我必须在多项式时间内猜对。究竟是哪一个呀。“在这个题中,找一个解很困难,但验证一个解很容易。验证一个解只需要O(n)的时间复杂度,也就是说我可以花O(n)的时间把我猜的路径的长度加出来。”这句话似乎说,我只需要随便给个解,验证它对不对就够了。而后面的意思似乎又是说必须要找对。感觉有点懵。

  • 磁性开关

    学过一点,但是不是很懂。。。

  • zy498420

    博主能否解释一下,如何能在多项式复杂度,检验某个数字电路一定不能输出”true”?我可真没想出来,为什么“它显然属于NP问题”??

  • paw

    回83楼,其实这个电路问题就是可满足性问题
    具体怎么证明,自行Google吧,,,

  • pengdlzn

    拜读了,受益匪浅啊!

  • Ciocio

    博主的文章写得很好 受益匪浅啊 感谢博主的分享

  • 非花非雾

    根据文章能够了解很多的东西了,谢谢

  • ufo

    博主文章很好,终于明白p、np还有npc了……

  • leon

    考算法前来看的博文。
    写的文非常棒。
    点个赞。

  • thomas

    从google敲NP问题进来学习的,想提出一个问题,一直没找到解释

    假设逻辑电路 or and xor输入信息为2个各1bit,输出为1bit
    是不是可以说信息经过这样的逻辑电路后有损失
    知道输入和输出很容易验证,但只知道输出想推出输入几乎不可能
    因为逻辑电路有信息丢失,这丢失的信息到哪里去了?
    除了遍历以外有没有办法快速的从输出导出输入,已知逻辑电路的情况下.

    这个问题是从MD5被破联想到的,目前只有差分统计手段,想在理论上找到更好的方法.

  • Jak Wings

    流程图没有用全角空格,全乱了……

  • waytofall

    顾大牛你好,对你博文中一点表述比较不认同。我百度的结果,旅行商问题(TSP)是在图中找到经过所有点且距离最小的回路,而汉密尔顿回路问题是寻找一条汉密尔顿回路或回答图中是否存在汉密尔顿回路,那么实际上如果图中的权值(距离)大于0小于正无穷的话,汉密尔顿回路问题应该转化为“旅行商问题是否存在不是正无穷的解”(这个我是从最短路径问题引出来的)。
    或者,按楼主的定义,将原图中所有路径权值定义为0,对每个顶点给其在原图中不邻接的其他顶点添加一条权值为1的路径,问题应该转化为“新图中的TSP路径是否为0”。

  • waytofall

    顾大牛你好,对你博文中一点表述比较不理解。我百度的结果,旅行商问题(TSP)是在图中找到经过所有点且距离最小的回路(找寻最短汉密尔顿回路),而汉密尔顿回路问题是寻找一条汉密尔顿回路或回答图中是否存在汉密尔顿回路,那么实际上如果图中的权值(距离)大于0小于正无穷的话,汉密尔顿回路问题应该转化为“旅行商问题是否存在不是正无穷的解”(这个我是从最短路径问题引出来的)。
    或者,按楼主的定义,将原图中所有路径权值定义为0,对每个顶点给其在原图中不邻接的其他顶点添加一条权值为1的路径,问题应该转化为“新图中的TSP路径是否为0”。

  • lijinma

    看懂了,感谢;收获很多;

  • 小粽子

    对于NPC问题,如果想要找到近似最优解的话,大概需要用什么样的算法呢。

    • ika

      很多群体算法在NPC寻优都有很不错的表现,比如蚁群算法,粒子算法等

  • airwindow

    This is a great article to explicitly introduce NP related concepts.

  • ferran

    感谢博主,条理清晰,通俗易懂,豁然开朗。

  • Felix

    看算法导论的英文版和中文版都看得云里雾里,博主的文章讲的清楚多了,受教了!

  • jxxiangwen

    了解了,谢谢博主。

  • 学习

    忍不住要评论 您讲的太好了 看了两本算法书 但是NP完全问题总是看不下去 今天看您的讲解如醍醐灌顶啊 谢谢博主

  • lyy

    赞写法,赞分享精神

  • mm豆

    lz真的大神!谢过了

  • ru0chen

    九年过去了,赞一下!

  • 哈哈

    谢谢楼主这么认真的解释。 总算看到一个能解释清晰的人啦。找了很多地方,大家解释NPC都很不清楚,我一直不理解完全 是个什么意思。谢楼主

  • gentlewolf

    受教了!

  • Rolaheart

    Thanks. Very clear.

  • 蛮蛮

    佩服!

  • sasa

    到此一游,膜拜

  • 阿may

    楼主简直神人,讲解的深入浅出
    文科生+数学渣+it盲竟然完全看懂了。

  • 巴呐呐

    给你10000000个赞

  • 春风化雨

    受教了,谢谢

  • 7orange

    写得很清楚,学习了!

  • Mercy

    谢谢博主!豁然开朗的感觉!

  • 公子小白

    非常感谢博主,写的非常通俗易懂。突然让人明白知识的难易程度不仅仅取决于知识本身的难度系数,更取决于讲解这个问题的人的水准。
    只是有一点不明白,你上面说一元一次方程可以归约成一元二次方程。如果我令一元一次方程x平方项的系数为0,可以理解为转化成了一元二次,可是一元二次方程求解公式是不能让平方项系数为零的。这里不太明白,博主能否讲解一下

    • 圣诞快乐

      可以这么认为,你的”一元二次方程求解公式”其实是“平方项不为0的一元二次方程求解公式”,不是完备的。

  • 飞够来嘿够来

    原文有一处表述有点歧义——“这个规则即是:两个方程的对应项系数不变,一元二次方程的二次项系数为0。” 改变的应该是一元一次方程,便于理解可以阐述为 “将一元一次方程加上系数为0的二次项”。

  • 拟好

    讲得不错,受益匪浅

  • aaaaabbbbc

    受益匪浅,楼主果然厉害

  • aaaaabbbbc

    就是有一个问题,如何证明一个问题是NP呢,找到一个问题的多项式算法感觉也不简单

  • aaaaabbbbc

    Matrix67神经病 傻比 神经病 傻比 神经病 傻比 精神病 煞比 神经病 傻比 精神病 煞比 神经病 傻比 精神病 煞比 。证毕。

  • 讲的太清楚了!

  • ceclinux

    讲的漂亮,谢谢

  • xiaoying1990

    个人感觉,如果tsp是给定一个预算c,要求得到的结果不超过c,那么它是一个npc问题,因为容易验证它属于np,而如果是要求最优解,则无法在多项式时间验证它吧…所以就变成了nph

  • 金良山庄

    博文写的不错。缺点也有,太多理论叙述,没有形象生动的例子,可以看做重中之重的规约方法也没有细讲。 于此相对应,这里推荐一篇博文《 P问题、NP问题、NPC问题的概念即实例证明》附链接http://blog.csdn.net/u012176591/article/details/51470999 。

  • ra

    我想这一句有误:“NP问题并不是那种“只有搜才行”的问题,NPC问题才是。”
    正确来说,应该是“NP问题并不是那种“只有搜才行”的问题,非P的NP问题才是。”

  • yy

    非常感谢博主这篇文章的讲解。但自己有个地方没有理解,就是文中说“试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了,因为除非你试过所有的路,否则你不敢断定它“没有Hamilton回路”,这里提到该问题不是一个NP问题,那如果我猜到并验证了一条Hamilton回路,是否问题得解而不需要尝试所有的路径呢?请恕愚钝。

  • daisie_q

    学历史的文科生来这里看天书。但是完全被博主的聪明迷倒。

  • GTMer

    赞赞赞,看密码学的时候讲到P NP,前来补习。

  • souloikj

    谢谢楼主!!!刚刚开始看N和NP的问题。。。看wiki看的一头雾水,到您这看完就理解了

  • Ciruelas

    谢谢您!直到看到您的这篇文章,我才搞清楚这几个概念。自己理解书上的定义不知道要走多少弯路!

  • Dark

    一个困扰了我两年的问题,看了大大的文章,瞬间明白了。。果然翻译算法导论的人还需要修炼修炼啊!然后发现近几年的回复多了很多!以下是回复数量:
    2016: 15
    2015: 17
    2014: 8
    2013: 11
    2012: 5
    2011: 17
    2010: 10

  • benjamin

    受教了~~

  • Ginshac

    刚学到p/np/npc 问题,看到楼主写的豁然开朗!多谢!

  • Trump

    非常感谢楼主,这真的是一篇通俗易懂的文章

  • t1ger

    TSP问题是 NP-Hard 问题,不是 NPC 问题

  • Don

    好文章!!!太棒了。。真的通俗易懂啊。看algorithm design看得云里雾里。还是博主说的清楚啊。

  • lrcray

    神文膜拜!

  • MattYang

    好文

  • eric

    10年前的好文,受教了

  • 河童

    今天还有人回复,握手,可不可以讨论下NP问题的定义,博主写的是可以在多项式时间内验证一个解与可以在多项式的时间里猜出一个解的问题。这里的验证是说,我随便给一个解,只要在多项式时间内验证它正确与否还是说我必须在多项式时间内猜对。究竟是哪一个呀。“在这个题中,找一个解很困难,但验证一个解很容易。验证一个解只需要O(n)的时间复杂度,也就是说我可以花O(n)的时间把我猜的路径的长度加出来。”这句话似乎说,我只需要随便给个解,验证它对不对就够了。而后面的意思似乎又是说必须要找对。感觉有点懵。

  • shualliu

    真的讲的很好,总算领悟了

  • liuruoze

    写得很好,很清晰,赞一下。

  • qiguo

    写的很好,受教了!

  • dessasic

    非常好。

  • hollysiguoyi

    有一个地方不是很理解,逻辑电路本身就有无穷多种,无穷多的NP问题约化到逻辑电路上也就有无穷多的逻辑电路问题,又不是约化成同一个逻辑电路,为什么把逻辑电路问题只当作一个问题(NPC问题)?

    • Germinate

      我来解释一下。所有的逻辑电路问题(下面称之为逻辑表达式),都可以约化(归约)到一个问题,就是3-SAT问题。即逻辑表达式由N个子表达式用 OR 连接,子表达式内部用 AND 连接,每个子表达式包含3个变量。
      所有的逻辑表达式都可以归约为3-SAT问题,证明见:http://faculty.math.tsinghua.edu.cn/~zwang/netopt/articles/res2.html
      由此,所有逻辑电路问题都是一个问题。

  • 匿名

    请问有人知道(谷歌官方应用市场)”数学家的游戏”吗?
    谁分析过里头的npc猜想算法?

  • 小乐乐

    写的太好了,必须留个言。之前怎么也弄不懂这几个的概念,百度也能找到一堆答案,但大部分都是互相引用,看不懂。这个是我见过的介绍的最明白的!

  • 阿飞

    大神我可以转载吗,这个太厉害了

  • yoyoqgn

    服服服,看到这是2006年的文章,但是是我至今为止读到最好的讲述NP 问题的博客。非常清晰,学习了

  • ich

    可以参考《计算理论导引》,该书详细解释P和NP的形式化讲义,而且非常通俗易懂。读完之后才知道P和NP的真正含义,以及为什么 NP叫做“非确定性多项式时间”,而不是叫做”非多项式时间“。P和NP是从图灵机推导出来的。

  • DavidLi

    真的很厉害

  • timy

    这篇文章真是必须要安利一下, 思路清晰, 文笔流畅, 佩服佩服, 让我弄明白了啥叫NP, P, NP-HARD, NPC 这些经常看见 却不熟悉的概念. 非常感谢

  • 匿名

    很好的文章,赞一个

  • 匿名

    转眼过去十多年了,从谷歌上搜到这篇经典的博文。
    大赞博主!

  • LightGal

    思路清晰,受益匪浅。敢问博主现在在从事什么事业?

  • 从来只能拿到胸牌的蒟蒻

    膜一下神犇,豁然开朗

  • 凌幽

    豁然开朗
    可以加一下QQ吗神犇
    QQ2743160120

  • 渔先森

    大赞博主!!!整篇看下来,通俗易懂。受教了

  • 渔先森

    “既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。”NP问题是只能在多项式时间内找到一个解,如果所有NP问题都解决了,也只能说明对一个P类问题,能在多项式时间内得到验证,但并不能说明能在多项式时间内求解。。不理解”此时NP就等于P“,求博主解答

  • c0099

    机缘巧合考前看到这篇,感谢博主!

  • Jawinton

    居然是十年前的文章让我明白了NP问题

  • zsxh

    真是赞啊,我来的太晚了,这个问题困扰我好长时间了

  • windseraph

    11年前的文章,太厉害了,感谢

  • bobble

    谢谢,顺便手残修复一下那两个逻辑电路的图片qwq

  • 666

    博主强调一下以上问题的前提都是判定类问题。

  • 戈戈

    非常感谢博主精辟的论述,比网上绝大部分的搬运博文好太多了

  • Cookie

    懂了!!谢谢博主

  • 小马子

    谢谢博主的回答,逻辑清晰,把复杂的问题讲的很简单。PS:提一个小建议,如果文末可以配一个集合关系图:P、NP、NPC,NP-hard问题的关系图,就更清晰直观了

  • BurningBear

    博主讲的太棒了! 十分感谢!

发表评论