什么是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原创
转载请注明出处

364 条评论

  • 那么那么地

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

  • 懒羊羊

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

  • 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“,求博主解答

    • lyminghao

      这里的“解决”意思是找到了多项式求解的算法,因为NPC可以多项式求解,所以所有NP都可以多项式求解了,就都是P了。

  • c0099

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

  • Jawinton

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

  • zsxh

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

  • windseraph

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

  • bobble

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

    • Boyang

      You do not have permission to get URL ‘/cnblogs_com/tonylim/958887/o_02.PNG’ from this server.

  • 666

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

  • 戈戈

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

  • Cookie

    懂了!!谢谢博主

  • 小马子

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

  • BurningBear

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

  • crystal

    博主太厉害,再夸夸你,不怕你骄傲。这么复杂的关系,能这么通俗易懂地把我们讲明白。厉害了。

  • Kent

    考前打卡,其实已经看了第N遍了,写得我挑不出任何一点点毛病。真的感谢博主,顺带明天考试求一点光环。
    博主是我中学开始从事OI就听闻的大神。真的很感激

  • Jet

    厉害 佩服

  • void

    看完懂了!谢谢博主!

  • void

    看完懂了!谢谢博主!

  • 张连聘

    感谢博主分享自己的思考,对P,NP,NPC 有了基本的要点认识。

  • 一路向北

    12年考古~ 很有帮助

  • 银蓝羽翼

    看完懂了,谢谢博主。但约归那里是不是一开始AB有几处写反了啊?

    • 银蓝羽翼

      准确点说,是这段
      “‘问题A可约化为问题B’有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难,因为解决前者的方法可以用来解决后者。”
      里,为什么B时间复杂度低了还能解决A?

    • oak

      实际上是“B的时间复杂度高于或者等于A的时间复杂度”。只是为了证明这一点用了反证法,假设B的时间复杂度比A低,那么A的算法可以改进为B的算法,此时A的时间复杂度又与B相同了。所以结论是问题B的时间复杂度不低于问题A。

  • 小虫sir

    遍寻谷歌百度,就数楼主这篇最透彻!

  • 李万胜

    我觉得还是没有说明白NPC问题,NPC问题到底是一个问题还是一类问题,是一类NP问题可以归约到一个NPC问题,还是所有NP问题都可以归约的一个NPC问题,还是所有NPC问题都可以归约到一类NPC问题,还是不知道有没有一个NPC问题存在?

  • 小黎

    没看懂。我这么理解大神的这篇文章的:
    1 复杂度的问题。实质是问题大小和算法所需时间的增长速度关系,从而引出“多项式时间”。
    现阶段,有现实意义的是“找到能在多项式时间内解题的算法”。

    2 由此而来,可知:
    P问题就是 可以“在多项式时间内”解得的问题。(在多项式时间内有算法)
    NP问题就是 不可以“在多项式时间内”解得,但可以“多项式时间内”猜到/验证到某个解的问题(没有多项式时间复杂度的算法。或者说,有算法但一定超出多项式时间,举例,阶乘)

    3 到这里开始有点乱了:
    引入“约化”的概念,本质是增加复杂度换取不同类问题的“(通用算法)”,即牺牲效率换得算法通用性。)前文说了复杂度大致有两个级别,多项式级别,和多项式之上的级别。NP问题不是不存在算法,而是不存在多项式级别复杂度的算法。所以约化的概念和复杂度的概念两者关联我没能理解。随着约化的传递,复杂度从多项式变成多项式之上,问题从P到NP再到NPC,那么就算找到了所谓复杂度最高的NPC的算法,也只证明了NPC可以变为NP,不能证明NP=P,因为你没说这个复杂度是不是多项式复杂度。而前面你也说了,不是所有的问题都都可以多项式时间内求解,这不已经说明NP不是P了吗

    • nooon

      NP问题不是不存在多项式算法的问题,而是不一定存在多项式算法的问题,但肯定能在多项式时间内验证一个解是否为该问题的解。

  • Naylon

    12年过去了,看完后依然受益。谢谢博主

  • lewyn

    谢谢博主= =
    这逻辑比很多大学老师上课都要好啊,既懂又能讲清楚实在是太重要啦

  • hpc

    豁然开朗,赞

  • Neo

    我的天,博主写这篇文章的时候,我还在玩泥巴呢~如今才来膜拜,😯一定好好科研

  • RainyH2O

    读了好几遍了,确实好文章,最早的时候仿佛读天书,每读一遍加深一遍理解,现在终于能基本理解全文了

  • icecream

    太厉害了吧,看懂了一部分

  • aiqlee

    我也膜拜一下

  • virtualman

    感谢博主,这篇文章讲的非常深刻,很适合夜深人静的时候,静静地思考,反复读了三遍终于理解了,这可以说是一篇很深刻的文章了,谢谢!

  • Phoebe

    太好了受用啊

  • 小磊

    博主厉害!偶然搜到了这篇博客,受益良多。

  • 野猪佩奇

    感谢博主~讲的很透彻~赞!

  • aabb

    读了不知多少介绍np的文章,从来不懂。就这篇一下子明白了。谢谢!!

  • zryabc

    十几年前的神文,膜拜一下

  • CaptainSlow

    我居然全部看完而且看懂了!感觉博主的文章都写得超级棒啊!多谢多谢!

  • 水风车

    先收下了……刚开始学习计算机科学。

    • 水风车

      今天我看完了这篇文章。受益匪浅。希望博主能够维护下网站,开放其他文章。

  • jobs.jia

    你这个评论为什么不搞分页?大神都这么任性?

  • Boyang

    博主,那两个逻辑电路的乱了!能否更正一下!

  • 小强

    博主为什么我再这里找不到你的名字而且你别的文章去哪里找我也不知道,有谁能告诉一下吗?

  • 喵喵

    想不到这篇文章已经是12年前写的了…

  • 查里里

    前来膜拜,太赞了!

  • draftbk

    厉害呀,感谢!

  • 帅虎

    16年的时候我还在高中,单纯因为有意思而喜欢看博主的文章。如今大三上算法课,不太理解NP问题,偶然搜到博主的文章,依然使人豁然开朗,但发现最新博客依然还是16年时的那个。这样的文章不好写,大家且看且珍惜。

  • 听见涛声

    偶然看见文章,受益匪浅

  • wuliytTaotao

    真的牛逼,学到了

  • IP

    感恩大神愿意花时间写,膜拜膜拜,真心牛啤,讲的太好了!

  • 旗木

    楼主请问关于the halting problem的讲解还有吗

  • eric

    楼主讲的真好,就是为啥不更博了呢?

  • Mango

    太厉害了!比很多白话理解的科普文更科普,更易懂,不得不佩服大神!太扎实的基本功了

  • linner

    2019年的打卡

  • 别问我是谁

    养家糊口不易啊。。不更新了 哭唧唧

  • zzm

    再膜拜一下

  • Maxwell

    TQL!

  • curled

    支持一波!写得真棒~

  • Maxwell

    写得超棒啊!

  • rz

    厉害厉害!
    “有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题。”
    这里看不懂,Hamilton ,TSP问题如何归约为逻辑电路问题?

  • rz

    厉害厉害!
    “有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题。”
    这里看不懂,Hamilton ,TSP问题如何归约为逻辑电路问题?
    不知道能否还有人恢回复, 手动尴尬~

  • MoodyOrange

    网页中逻辑电路部分的代码需要处理一下,是乱的

  • MikyLo

    谢谢楼主!快十三年了啊。

  • 哀蕊课学算法

    经典的东西经久不衰,博主这篇文章的确精彩

  • shadow

    我去年冬天看过,那会儿做课题才开题,今年已经在修改润色语言,感谢这篇文章对我问题分析部分的帮助,表示感谢的同时还有个小小的请求,能不能提供几篇经典的参考文献,当然我也知道能提供参考文献的人很多,能把问题将的这么清楚的人还挺少的。

  • Mogician_Jeff

    佩服,看了博主好几篇文章,都又有条理又生动,作为门槛较高的科普文章着实不容易。

  • Phecda

    谢谢博主,让我彻底明白了这些问题
    博主的这篇文章也是我见过的最隽永的,时隔13年了,评论不断

  • leon

    讲得不错,感谢。

  • LAN

    NP问题真的是数学史上的璀璨之星,谢谢大牛的讲解,仔细看一遍基本都懂了,十三年无数人的浏览,数学还真是个奇妙的东西

  • 朋友鸡

    懂了!谢谢。

  • Nota

    相见恨晚的好文章.
    不过还是有个疑问,不知道能否得到解答,还是写出来吧:
    “那么只要任意一个 NPC 问题找到了一个多项式的算法,那么所有的 NP 问题都能用这个算法解决了,NP 也就等于 P 了”这几件事情之间都是当且仅当的关系吗?换句话说,能不能绕开NPC问题这个硬骨头,在没法为NPC问题找到多项式算法的前提下,也能为NP问题找到多项式算法?毕竟NPC问题是NP问题约化得到的,难度更大.

    • 兔撕鸡

      路人理解:NP问题包含P和NPC。为了证明所有的NP问题等不等于P问题,才引入了NPC。NP问题一个个证明的话绕不开NPC问题的证明,而NPC问题证明成功则可说明所有的NP问题都存在多项式时间算法。

  • 若尘

    这么多年了,经久不衰,数学可真是奇妙,谢谢楼主

  • 铠甲

    真的经久不衰

  • 将将好

    十几年前就已经如此通透了!

  • Steven Shi

    很强!!

  • 扶习兮拟排忧

    博主好强!!科普的文章十分生动有趣!

  • 枫零

    您就是神……真的是通俗易懂
    关于cook定理,可不可以这样理解:
    cook找到了第一个NPC问题SAT,如果能证明SAT是P问题,那么因为NPC可以规约所有的NP问题,所以得以证明,所有的NP问题都是P问题,即P=NP?

  • PPeng

    深入浅出,豁然开朗,受益匪浅 —— 来自2020年的膜拜。

  • 我是花花啊

    受益匪浅

  • 刘御风

    来自14年后的膜拜!太强了

  • sxz

    年年有评论,不愧是matrix67

  • Zoom

    来自十五年后的评论,醍醐灌顶。

  • 哈哈

    我想问下,你现在过得好吗,不知道学术这条路该不该走

  • tsingakbar

    06年的时候我已经经历了NOIP的失败安心参加高考了。不想15年后已经是个大龄程序员的我又搜到了大神深入浅出的解析。

  • 木鱼

    一位高中生对NP与P问题的猜想。
    旅行商问题(Travelling Salesman Problem),即寻找从一个城市到另一个城市的最短路线,答案非常容易验证,不过,如果P≠NP,就没有计算机程序可以迅速给出这个答案。
    其实,可以猜想,首先,旅行商问题(Travelling Salesman Problem),即寻找从一个城市到另一个城市的最短路线,可以想向这些城市,就是无数个点。空间无数个点,用几何算法,是可以快速用数学解出最快的遍历方式。就是各个点的首尾相连,平面来说,各个点的首尾相连,刚好是这几个点组成的多边形图形边线(用几何,两边之和大于第三边的逻辑进行推理。)。
    而对于空间无数个点来说,你可以想象各个点是一个个粒子,如果借用光的双缝干涉实验,和量子的波粒二象性,这些点最快的遍历方式,也可以找到存在一个多项式时间的算法,快速进行遍历,猜想,这些空间的点,快速遍历的结果,就是一个由覆盖各个点的立体的不规则图形面(不是平面,是波形不规则的面,但可以用粒子的镜像为不规则平面)。
    波的传送及粒子的纠缠,告诉我们,快速的遍历,不能用普通数学和力学来解答,这也是为什么,对于量子计算机的各种算法和处理,不能用常规的思路去思考和想象。而可以用波的特性和粒子纠缠来解读。也许,上帝,给了问题,就必定会有一个答案在某个地方,只是你还没发现而已。

  • 木鱼

    一位高中生对NP与P问题的猜想。
    旅行商问题(Travelling Salesman Problem),即寻找从一个城市到另一个城市的最短路线,答案非常容易验证,不过,如果P≠NP,就没有计算机程序可以迅速给出这个答案。
    其实,可以猜想,首先,旅行商问题(Travelling Salesman Problem),即寻找从一个城市到另一个城市的最短路线,可以想向这些城市,就是无数个点。空间无数个点,用几何算法,是可以快速用数学解出最快的遍历方式。就是各个点的首尾相连,平面来说,各个点的首尾相连,刚好是这几个点组成的多边形图形边线(用几何,两边之和大于第三边的逻辑进行推理。)。
    而对于空间无数个点来说,你可以想象各个点是一个个粒子,如果借用光的双缝干涉实验,和量子的波粒二象性,这些点最快的遍历方式,也可以找到存在一个多项式时间的算法,快速进行遍历,猜想,这些空间的点,快速遍历的结果,就是一个由覆盖各个点的立体的不规则图形面(不是平面,是波形不规则的面,但可以用粒子的镜像为不规则平面)。
    波的传送及粒子的纠缠,告诉我们,快速的遍历,不能用普通数学和力学来解答,这也是为什么,对于量子计算机的各种算法和处理,不能用常规的思路去思考和想象。而可以用波的特性和粒子纠缠来解读。也许,上帝,给了问题,就必定会有一个答案在某个地方,只是你还没发现而已。
    也许,P问题,只是NP问题当中的一种,P问题,不是基于量子计算机的一种模式。

  • 木鱼

    一位高中生对NP与P问题的猜想。
    旅行商问题(Travelling Salesman Problem),即寻找从一个城市到另一个城市的最短路线,答案非常容易验证,不过,如果P≠NP,就没有计算机程序可以迅速给出这个答案。
    其实,可以猜想,首先,旅行商问题(Travelling Salesman Problem),即寻找从一个城市到另一个城市的最短路线,可以想向这些城市,就是无数个点。空间无数个点,用几何算法,是可以快速用数学解出最快的遍历方式。就是各个点的首尾相连,平面来说,各个点的首尾相连,刚好是这几个点组成的多边形图形边线(用几何,两边之和大于第三边的逻辑进行推理。)。
    而对于空间无数个点来说,你可以想象各个点是一个个粒子,如果借用光的双缝干涉实验,和量子的波粒二象性,这些点最快的遍历方式,也可以找到存在一个多项式时间的算法,快速进行遍历,猜想,这些空间的点,快速遍历的结果,就是一个由覆盖各个点的立体的不规则图形面(不是平面,是波形不规则的面,但可以用粒子的镜像为不规则平面)。
    波的传送及粒子的纠缠,告诉我们,快速的遍历,不能用普通数学和力学来解答,这也是为什么,对于量子计算机的各种算法和处理,不能用常规的思路去思考和想象。而可以用波的特性和粒子纠缠来解读。也许,上帝,给了问题,就必定会有一个答案在某个地方,只是你还没发现而已。
    也许,P问题,只是NP问题当中的一种,P问题,只是刚好符合常规计算机又符合量子计算机的一种模式。如同正方形与长方形的关系。而随着量子计算机的大量应用,相信更多的解和答都会用全新的思考方式来解决各种新的问题。

  • dejavu

    讲得太清晰了!

  • 余风

    2021年,最近开始看算法,看到大佬的这篇文章,获益匪浅。感谢。

  • jjjj

    受益匪浅!

  • 风铃Flonggo

    感谢!08年(13年前)我应该才三年级~~~太强了

  • m7996

    前来膜拜

  • young

    2021年前来考古,膜拜大佬Orz

  • PJ

    2021年过来考古,讲的太好了,豁然开朗,膜拜

  • 小菜鸡

    豁然开朗

  • 飞翔的葱油饼

    确实牛

  • 长门

    可以可以,一直稀里糊涂的,记了又忘,现在是真的明白了,太强了!!

  • aa

    感谢博主!!!

  • hs

    受益匪浅;看到作者现在还在更新博客,就更加吃惊了。博主换过人吗?如果没有,现在在大学还是企业工作?

  • CB

    本科生前来膜拜大佬

  • Issca Zhang

    牛比!

  • yhj

    真的太厉害了,2022年7月31前来围观

  • yhj

    真的太厉害了,2022年7月31前来围观.

  • 机器人

    天才基本法竟然讲P=NP

  • ShaoJia

    orz讲得太好了,但是逻辑电路的图炸了,是否考虑修一下?

  • Quick play with mydildo

    Thahks tto my faather wwho informed me about this website, this weblog is really amazing.

  • dev.xxxcrunch.com

    Yoou acttually make itt appeaar so easzy together with youur presentation however I find thks
    topic tto bbe really one thing hich I bellieve I might never understand.
    It kijd of feels too complicated and very broad for me.
    I’m having a look forwad to yyour next publish, I’ll
    try to geet the hkld off it!

  • Aprill

    Hello every one, here every one is sharing such
    know-how, so it’s fastidious to read this webpage, and I used to pay a visit
    this webpage daily.

  • antje

    My partner and I absolutely love your blog and find nearly all of your
    post’s to be exactly I’m looking for. Would you offer guest writers to write content in your case?
    I wouldn’t mind creating a post or elaborating on most of the subjects you write
    concerning here. Again, awesome blog!

  • site

    Study about the innovations thatt can bring the payment
    market place too the future.

    Look at my web page: site

  • 오피사이트

    Can I show my graceful appreciation and show back my secrets on really
    good stuff and if you want to have a checkout Let me tell you a brief about how to
    get connected to girls for free I am always here for yall you know that right?

  • 대출 몽

    If you never ask for one more, it will not be interested in aiding you aany longer.

    Also visit my site: 대출 몽

  • webpage

    A personal loan is an installment loaqn from a bank or
    credit union.

    Here is my website; webpage

  • 웹툰 미리 보기

    What’s Taking place i am new to this, I stumbled upon this I’ve found It positively
    helpful and it has helped me out loads. I am hoping to contribute &
    help different users like its aided me. Good job.

  • 바카라사이트

    We are a bunch of volunteers and starting a brand new scheme in our community.
    Your site offered us with helpful info to work on. You’ve
    performed a formidable activity and our whole group shall be
    thankful to you.

  • 추가대출

    Fillimg out the basic on the weeb application can get you access to funds inside
    24 houurs oof approval.

    Here is my web site 추가대출

  • gorip.sasugawiki.com

    Table gamss also feature at SuperSlots and involve a number
    of blackjack, roulette, and casino poker games.

    Feel free to surf to my site :: gorip.sasugawiki.com

  • 레깅스알바

    The Bank oof Korea currently forecasts the annual unemployment
    prie at 3.9% for this year and three.8% for next.

    Feel free tto surf to my web page: 레깅스알바

  • more info

    Ahaa, its pleasant dialogue on the topic of this article at this place
    at this weblog, I have read all that, so at this
    time me also commenting at this place.

    Feel free to surf to my web page more info

  • 토토사이트

    Their portfolio of gaames and events keeps expanding every couple of weeks.

    my web page; 토토사이트

  • hts 판매 임대

    fantastic publish, very informative. I’m wondering why the
    opposite specialists of this sector don’t understand this.

    You must proceed your writing. I’m confident, you have a great readers’
    base already!

  • web page

    BetMGM WV and SICasino have the biggest no deposit bonus in the US.

    My website – web page

  • web site

    When a tribe wants to offer gambling on its lands,
    federal law demands that thhe state negotiate a compact with the tribe.

    my blog web site

  • 오피

    I believe people who wrote this needs true loving because it’s a blessing.
    So let me give back and show my inside to change your life and if you want to seriously get to hear I will share info about how to get connected to
    girls easily and quick Don’t forget.. I am always here for yall.
    Bless yall!

  • 강남 오피

    Let me give you a thumbs up man. Can I tell you exactly how to do
    amazing values and if you want to seriously
    get to hear and also share valuable info about how to become a millionaire yalla lready know follow me my fellow commenters!.

  • HZ

    Hey very nice blog!

  • 范捷琦

    高中的时候没弄太明白,终于看明白了些,感谢。

  • Marcos el Ruptor

    For a problem to have O(exp(N)) solution, its description must be O(exp(N)) in size.
    I’m sorry I can’t participate more in this discussion. I don’t speak Chinese (yet).

  • dhlolo

    很强,远古打卡

  • Tibrella

    牛啊!描述和逻辑都很清晰!

  • 인천출장마사지

    This article resonated with me on a personal level. Your ability to connect with your audience emotionally is commendable. Your words are not only informative but also heartwarming. Thank you for sharing your insights.

  • ai-porn-art.com

    Hi there to all, how is the whole thing, I think
    every one is getting more from this web site, and your views
    are nice in support of new viewers.

  • ConorCoxxx-Aunties panties_with Chery Leigh

    We stumbled ober here fro a different websiute andd thought I mmay ass well checxk things out.
    I lke what I see sso i am juet following you.

    Loook forward too loiking over your web paqge yet again.

  • rinevard

    很好的blog,爱来自中国❤️

  • 부산출장

    Standing outside the modern, minimalist exterior of the US State Department’s Harry S.
    방문출장안마

  • 부산출장안마

    Truman Building in the nation’s capital, it’s difficult to picture the ornate reception rooms on its seventh and eighth floors.
    홈출장마사지

  • 출장안마

    It’s a dichotomy outlined in the opening pages of the new book “America’s Collection: The Art and
    출장스웨디시

  • webpage

    Если вам нужен надежный компас в мире цифровых изменений дизайн сайтов немкович дизайн был создан с целью заботы о
    вашем бизнесе
    Наши услуги, просто и понятно:
    1. SEO – улучшение видимости:
    Мы поможем вашему сайту быть легче найденным в интернете, чтобы
    вы могли находить нужную информацию без лишних усилий.

    2. PPC – реклама, которая работает: Наши
    рекламные кампании созданы,
    чтобы привлекать вас к тому,
    что вам действительно интересно.

    Мы сделаем так, чтобы информация о вашем хобби
    или услугах была легко доступной.

    3. Соцсети – связь с близкими:
    Мы поможем наладить связь с вашими детьми и внуками через социальные сети, чтобы вы могли быть ближе к своей семье.

    4. Веб-разработка – удобство в интернете:
    Мы создаем удобные веб-сайты, которые помогут вам находить важную информацию и быть в курсе последних новостей.

    5. Аналитика – прозрачность: Наша аналитика позволит
    вам лучше понимать, как работает интернет, и какие изменения
    происходят в онлайн-мире.

    6. Контент – информация по интересам: Мы предоставим вам контент, который соответствует вашим интересам, помогая вам находить то, что важно
    для вас.
    дизайн сайтов немкович дизайн агентство, которое заботится о вашем комфорте и удовлетворении в интернете.
    Если вы хотите быть в курсе
    современных технологий и оставаться связанными с миром, обращайтесь к
    нам!
    Готовы узнать больше о том, как мы можем помочь
    вам справиться с вызовами интернет-века?
    Свяжитесь с нами прямо сейчас, и давайте сделаем ваш онлайн-мир более комфортным и интересным для вас!

  • 부산출장마사지

    up. Over time, some of these relics have found new life as fun and kitschy tourist attractions.
    부산출장마사지

  • 부산출장마사지

    And while iterations of such abandoned settlements are found on every continent, with varying manmade and natural
    부산출장샵

  • 출장마사지

    causes to blame, a new era of ghost towns is now emerging that, while eerie, feels far off from good touristic fun.
    출장마사지

  • Iona

    Every weekend i used to go to see this website, for the reason that i wish for enjoyment, as this this web page conations actually pleasant funny information too.

  • dutzhao

    很高兴,在复习算法考试的路上碰到了这篇文章。

  • Joy

    关于P NP NPC NP-hard概念解释的全网最强中文文章

  • L2

    强无敌,跨越时间的教学

  • Apress

    %%%,收藏了,以后来看,希望下一次能看懂些。

回复给 Daniel 取消回复

  +  37  =  40