去他妈的定义

基本上,那些“唬人”的东西,都是先入门、先进了门槛的人,为了跟其他人隔离出区别,显示出自己的认知很牛X,可以谈笑风生,绞尽脑汁想出来的定义和概念,弄得初学者云里雾里,晕头转向,这说的是什么玩意儿?比如本文要介绍的P问题,NP问题,就弄晕了一批人。虽然这些定义和概念,很大程度上,使得交流更流畅,但是初学者绝对不能死记概念,弄清本质才是要紧的事情。所有的定义和概念,都对应着实际的物理意义。打开世界的屋顶,任何学问其实都不是传说中的“高深”。

“值得攻克的问题的价值是通过抵抗而成为久攻不克来证明的。(Problems worthy of attack
prove their worth by fighting back)” — 皮亚特·海恩(1905-1996)

伟大的诞生

有人就有江湖,有人也就有开会。2000年,美国克莱数学研究所在巴黎的法兰西公学院,组织各路豪杰,召开巴黎千年大会(Paris Millennium Event)。大会当然没有中原的乔峰、慕容复,只有众多的数学家们,比如德国的大卫·希尔伯特,英国的迈克尔·阿蒂亚。大会的主题,当然也不是比舞和比武,不是比谁比谁牛x更聪明,而是这些数学家们,要证明自己不够牛x,所以他们公布了世界七大数学难题,又称千禧年大奖难题(这也可以看作是他们向智商不足的人群发起的挑衅),其中P与NP问题被列为这七大世界难题之首。截止目前,除了庞加莱猜想被解,其它依然扑朔迷离。

  • 复杂度类P与NP问题(理论信息学:计算复杂度)
  • 霍奇猜想(数学)
  • 黎曼猜想(数学)
  • 杨-米尔斯存在性与质量间隙(量子力学)
  • 纳维-斯托克斯存在性与光滑性(计算流体力学)
  • 贝赫和斯维讷通-戴尔猜想(数学)
  • 庞加莱猜想(数学,已被解决)

CMI实验室,NP和P还在被讨论

本文要介绍的,就是第一个难题。这要求读者,对算法有一些基本的认知。但是,也别被算法二字又给唬住了。算法其实可以简单得理解为做一件事情的一系列步骤。比如你现在要做菜,已经给了你炉灶,锅以及所有做菜的工具和材料,为了做出一道菜,你得知道第一步做什么,第二步做什么,直到菜被做完。
第一步:洗菜;
第二步:切菜;
第三步:热锅;
第四步:放菜;
第五步:抄5分钟;
第六步:装盘;
第七步:关火。
这七部就是你做菜的算法,当然这个做菜的步骤你可以稍加变化,比如第二步和第三步可以同时,你在切菜的时候,同时热着锅,每一个步骤都是要成本的,比如你可以认为每一步的成本就是五分钟的时间,把第二步和第三步合并,就节约了五分钟时间,这样就对做菜的算法做了优化。对应在计算机世界里,也是一样的。计算机执行每一步,也需要时间,一个优秀的算法,就是成本竟可能最低。

这是简单的理解,当问题规模很大时(也就是步骤变得很多的情况下),算法的复杂度不仅是表示解决问题的时间,而是时间增长得有多快,通常会用特殊的符号表示。

算法复杂度

要计算或解决一个问题,该问题通常有一个大小规模,用nn表示。 例如, 从nn个数里面找出最大的那个数,这个nn就是该问题的规模大小。怎么找?我们要比较n1n-1次才能得到结果,这个n1n-1就是所花的时间,也就是时间复杂度。再比如,将nn个数按从大至小排序,nn是其规模大小,若是我们按这样的方法:第一次从nn个数里找最大,第二次从n1n-1个数里找最大,以此类推,需要的比较次数就是n(n1)/2n(n-1)/2,称我们所用的方法为算法,称n(n1)/2n(n-1)/2 为该算法的时间复杂度。对于时间复杂度,当nn足够大时,我们只注重最高次方的那一项,其他各项可以忽略,另外,其常数系数也不重要,所以,n(n1)/2n(n-1)/2我们只重视nn的平方这一项了,记为O(n2)O(n^2),这就是该算法对该问题的时间复杂度的专业表示。

所有形如a*n^k+b*n^{k-1}+c*n^{k-2}……都可记为 O(nk)O(n^k) , 其中 a,b,ca,b,c 为常数, nkn^k表示nnkk次方,*为乘号,这样的复杂度称为多项式时间复杂度,若是时间复杂度形如knk^nkk为大于1的常数,或n!n!,或更大的nnn^n,就称为指数型时间复杂度。显然,当nn足够大时,指数型时间比多项式要大得多的多。

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

P问题 (Polynomial Time)

所有能用多项式时间(Polynomial Time)算法计算得到结果的问题,称为多项式问题,也就是P,或者PTIME,所有绝对不可能用多项式时间求解的可解问题,称为指数型问题nnn^n。当然,还有一类问题属于不可解问题,也就是说你无论花多少时间也不能得到解答。

NP问题(Nondeterministic Polynomial Time)

有这样一类问题,假使你得到了问题的解,我要验证你的解是否正确,我验证所花的时间是多项式,但是我不能确定求解该算法的解(我能力有限,找不到,但不代表不存在),可能有多项式算法,可能没有,也可能是不知道,这类问题称为NP问题。

P问题肯定是NP问题

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

NP问题一直都是信息学的巅峰。巅峰,意即很引人注目但难以解决。在信息学研究中,这是一个耗费了很多时间和精力也没有解决的终极问题,好比物理学中的大统一和数学中的歌德巴赫猜想等。

NP与P可能的两种关系

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

NPC问题(Nondeterministic Polynomial Complete)

规约算法

一个问题A,若可以用问题B的算法来解决,则两个问题存在归约关系(Reducibility)
若问题A可归约为问题B,则B的时间复杂度高于或者等于A的时间复杂度。或者说,问题A不比问题B难。因为,既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。

归约具有一项重要的性质:归约具有传递性。如果问题A可归约为问题B,问题B可归约为问题C,则问题A一定可归约为问题C。

把A问题归约为B问题的过程也是一种算法,任意一个程序A的输入,都能按这个归约算法成程序B的输入,使两程序的输出相同,那么我们说,问题A可归约为问题B。

规约的算法一般是在多项式时间内完成(Polynomial-time Reducible),不然没有意义可言。

通过不断的规约,问题的复杂度越来越高,就可以找到复杂度更广的问题,来解决复杂度低的问题。我们的想法是,各个NP问题之间是否存在偏序(基于复杂度排序 ABC...MA\leq B \leq C ... MAA问题可以规约到BB问题,以此类推,MM是顶点,不存在其他的问题NN以及规约算法,使得 MNM \leq N),那么,最复杂的NP问题就排在最后。 这个最复杂的问题,也称为NP-hardness问题(NP难)。那么问题来了,是否可以找到复杂度最高的问题MM,所有的NP问题都可以规约至MM? The answer is yes!

如果给出了解决MM问题的算法,那么,其他的NP问题都得到解决。而有趣的是,这样的MM存在很多个,也就是组成了一个集合,在这个集合内的问题,都称为NPC问题(注意:集合内的问题也可存在规约关系,也就是一个NPC问题,可以归约到另一个NPC问题)。所以,如果一个问题LL是NPC问题,那么这个问题满足以下两个条件:

  • 问题LL是NP-Hard(也就是所有NP问题都可以归约到LL);
  • 问题LL本身就是NP。

判断一个问题是否是NPC问题?

给你一个问题MM,要证明MM属于NPC问题,那么首先要证明MM是一个NP问题,再证明已知的一个NPC问题LL,可以归约到MM

总结

P问题:

  • 存在多项式时间的算法,输入规模nn, 最坏运行时间O(nk)O(n^k)

NP:非确定型多项式时间

  • 给我答案,能在多项式时间内验证答案对不对(√)
  • 给出多项式时间算法找到答案(x 找不到,并不是说不存在。)

NP-hard:

  • 如果一个问题L,任意一个NP的问题都可以多项式规约到L,则称L问题为NP-hard问题。(比所有NP问题难)

NPC(complete):

  • 问题L是NP-Hard;
  • 问题L本身就是NP,则称L为NP-C问题。