美剧《基本演绎法》(也就是美版“福尔摩斯”)第 2 季第 2 集中,两位研究 NP
问题的数学家被谋杀了,凶手是同行,因为被害者即将证明“P=NP
问题”,她为独吞成果而下了毒手。然而凶手的动机,并不是千禧年大奖难题那100万美元的奖金——解决了
P=NP
问题,就能够破译世界上所有的密码系统,这里面的利益比100万美元多多了。

原文地址:http://m.blog.csdn.net/csshuke/article/details/74909562

剧中只用了一句话来介绍 P=NP
的意义:“能用电脑快速验证一个解的问题,也能够用电脑快速地求出解”。这句过于简单的话可能让大家一头雾水,今天我们就来讲一讲
P vs. NP。

希望通过这篇文章可以不仅让计算机相关专业的人可以看懂和区分什么是P类问题什么是NP类问题,更希望达到的效果是非专业人士比如学文科的朋友也可以有一定程度的理解。

1、P(polynomial)问题

什么是P和NP?

图片 1《基本演绎法》S02E02
截图。

计算机科学的一个主要研究方向是提高各种算法的速度。尤其在当前火热的“大数据”概念下,算法速度更显重要。很容易理解,处理的数据越大,计算的耗时就越多。对于一个算法,人们能够分析出运算时间与数据量之间的大致函数关系,这个关系被称为时间复杂度,它定量描述了该算法的运行时间。

假设有 n 个数要排序。一个初级的冒泡排序算法所需时间可能与 n2
成正比,快一点的算法所需时间与 nlog(n)
成正比。在某些条件下,桶排序算法所需时间甚至只和 n
成正比。最不实用的算法就是输入的数字随机排列,直到出现完全有序的情况为止……记前三个算法的时间复杂度分别记为
O(n2)、O(nlogn) 和
O(n),最后的“猴子排序”(Bogosort)算法平均时间复杂度则达到了
O(n*n!)。

在上面的例子中,前三种算法的复杂度是 n
的多项式函数;最后一种算法的复杂度是 n 的阶乘,根据斯特林公式,n!
相当于指数级别的增长。当 n
特别小时,多项式级的算法已经快过指数级的算法。当 n
非常大时,人类根本看不到指数级复杂度算法结束的那天。自然的,大家会对多项式级别的算法抱有好感,希望对每一个问题都能找到多项式级别的算法。问题是——每个问题都能找到想要的多项式级别的算法吗?

在一个由问题构成的集合中,如果每个问题都存在多项式级复杂度的算法,这个集合就是
P
类问题(Polynomial)。这意味着,即使面对大规模数据,人们也能相对容易地得到一个解,比如将一组数排序。

“NP”的全称为“Nondeterministic Polynomial”,而不是“Non-Polynomial”。NP
类问题指的是,能在多项式时间内检验一个解是否正确的问题。比如我的机器上存有一个密码文件,于是就能在多项式时间内验证另一个字符串文件是否等于这个密码,所以“破译密码”是一个
NP 类问题。NP
类问题也等价为能在多项式时间内猜出一个解的问题。这里的“猜”指的是如果有解,那每次都能在很多种可能的选择中运气极佳地选择正确的一步。

不妨举个例子:给出 n
个城市和两两之间的距离,求找到一个行走方案,使得到达每个城市一次的总路程最短。我们可以这样来“猜测”它的解:先求一个总路程不超过
100
的方案,假设我们可以依靠极好的运气“猜出”一个行走路线,使得总长度确实不超过
100,那么我们只需要每次猜一条路一共猜 n 次。接下来我们再找总长度不超过
50 的方案,找不到就将阈值提高到75…… 假设最后找到了总长度为 90
的方案,而找不到总长度小于 90
的方案。我们最终便在多项式时间内“猜”到了这个旅行商问题的解是一个长度为
90 的路线。它是一个 NP 类的问题。

也就是说,NP 问题能在多项式时间内“解决”,只不过需要好运气。显然,P
类问题肯定属于 NP 类问题。所谓“P=NP”,就是问——是不是所有的 NP
问题,都能找到多项式时间的确定性算法?

有一则程序员界的笑话,就是有一哥们去google面试的时候被问到一个问题是:在什么情况下P=NP,然后他的回答是”当N=1的时候”。这是我第一次听说P=NP问题,大概是在临近毕业为找工作而准备的时候。
这几天科技类新闻的头条都被阿尔法狗大战李世石刷爆了,虽然我也不是AI专家,但是也想从普通人的角度来写点东西来聊聊这个有意思的事情,在搜集资料的时候又一次看到了NP问题,于是想开个小差,在写下一篇文章《AI是怎么下围棋的?》之前,先说说这个NP问题哈。
最简单的定义是这样的:
P问题:
一个问题可以在多项式(O(n^k))的时间复杂度内解决。
NP问题:
一个问题的解可以在多项式的时间内被验证。
NP-hard问题:
任意np问题都可以在多项式时间内归约为该问题,但该问题本身不一定是NP问题。归约的意思是为了解决问题A,先将问题A归约为另一个问题B,解决问题B同时也间接解决了问题A。
NPC问题:
既是NP问题,也是NP-hard问题。
这样的定义虽然简单,但是对于第一次接触P、NP的人来说,就像前一阵问你什么是“引力波”而你回答:引力波是时空的涟漪。从答案中几乎没有得到任何有意义的理解。所以接来来的内容希望不仅计算机相关专业的人可以看懂,希望达到的效果是文科生们也可以有一定程度的理解。
现阶段虽然电脑已经非常的普及,有人用它来上网,有用它来的游戏,有用它来看片,但是很少人有还在乎电脑的本质是计算机,它在给人们的日常生活带来娱乐和方便的同时表现的其实是其庞大的计算能力。日常生活中我们使用的各种五花八门的软件,其实都是一组计算机程序,而程序则可以看作是一系列算法,而我们看到的计算机的硬件的作用就是处理这些算法。这里的所说算法不只是简单的加减乘除,而是包括下面这些要素:
算术运算:加减乘除等运算
逻辑运算:或、且、非等运算
关系运算:大于、小于、等于、不等于等运算
数据传输:输入、输出、赋值等运算
以及通过控制结构来控制处理这些运算或操作的顺序。说到这里有点担心有些朋友已经不是很明白了,举个例子吧。
我们如何从n个数里面挑出最大的数。这个简单吧,就只需要一个一个数的对比过去就行了。具体说也就是先比较n和n-1,记下比较大的那个数,接着我们再比较记下的这个数和n-2,又记下比较大的数,这样一直比到最后一个数。这整个比较的过程我们就可以把其叫作算法,而这个算法就包含了上述的这些要素。给我们的n个数就是算法的输入数据,我们要挑选出最大的那个数就是算法的输出数据,当中我们判断大小的时候必然采用了一些基础的算术运算或关系运算。
希望说到这里大家能够基本理解什么是算法,因为接下来我要花一点时间说说什么是算法的时间复杂度。要计算或解决一个问题,该问题通常有一个大小规模,用n表示。我们还是引用上面的例子,从n个数里面找出最大的那个数,这个n就是该问题的规模大小。怎么找呢?我们要通过比较n-1次才能得到结果,这个n-1次就可以理解为所花的时间,也就是时间复杂度。再比如,将这n个数按从大至小排序,n是其规模大小,若是我们按照这样的方法:第一次从n个数里找最大,第二次从n-1个数里找最大,以此类推,需要的比较次数就是n(n-1)/2。我们所用的方法称之库为算法,那么n(n-1)/2就是该算法的时间复杂度。对于时间复杂度,当n足够大时,我们只注重最高次方的那一项,其他各项可以忽略,另外,其常数系数也不重要,所以,n(n-1)/2我们只重视n的平方这一项了,记为O(n^2),这就是该算法对该问题的时间复杂度的专业表示。
时间复杂度其实并不是表示一个程序解决问题具体需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。不管数据有多大,程序处理花的时间始终是那么多的,我们就说这个程序很好,具有O(1)的时间复杂度,也称常数级复杂度;数据规模变得有多大,花的时间也跟着变得有多长,这个程序的时间复杂度就是O(n),比如找n个数中的最大值;而像冒泡排序、插入排序等,数据扩大2倍,时间变慢4倍的,属于O(n2)的复杂度。还有一些穷举类的算法,所需时间长度成几何阶数上涨,这就是O(an)的指数级复杂度,甚至O(n!)的阶乘级复杂度。不会存在O(2n2)的复杂度,因为前面的那个“2”是系数,根本不会影响到整个程序的时间增长。同样地,O(n3+n2)的复杂度也就是O(n3)的复杂度。因此,我们会说,一个O(0.01n3)的程序的效率比O(100\*n2)的效率低,尽管在n很小的时候,前者优于后者,但后者时间随数据规模增长得慢,最终O(n3)的复杂度将远远超过O(n2)。我们也说,O(n100)的复杂度小于O(1.01n)的复杂度。
Ok,写到这里总算要引入正题了,容易看的出,前面的几类时间复杂度可以分为两种级别:一种是O(1),O(log(n)),O(na)等,我们把它叫做多项式级的复杂度,因为它的规模n出现在底数的位置;另一种是O(an)和O(n!)型复杂度,它是非多项式级的,其复杂度往往计算机都不能承受。
是时候引入P、NP问题的概念了:如果一个问题可以找到一个能在多项式的时间复杂度里解决它的算法,那么这个问题就属于P问题。而NP问题的理解并不是NotP,NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题,NP问题的另一个定义是,可以在多项式的时间里猜出一个解的问题。P类问题相信不用举太多的例子来说明了,上面提到的找最大数,排序等问题都是P类问题,而要更好的理解NP问题需要另外举一个例子。
大整数因式分解问题-比如有人告诉你数9938550可以分解成两个数的乘积,你不知道到底对不对,但是如果告诉你这两个数是1123和8850,那么很容易就可以用最简单的计算器进行验证。
最短路径问题-某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径——最短路径。

     
可以在以多项式表达的时间内按部就班的按照步骤求出确切解的问题,也就是说它的计算复杂度是一个多项式。我们通常用的O(n),O(logn),O(n2)等等类似的都是这类问题。

P会不会等于NP?

图片 2《基本演绎法》S02E02
截图。

这个问题目前还没有定论,当下学术界的大多数意见是
P≠NP。一个主要原因是,这么多年过去了,人们仍然没有找到解决上千个 NPC
问题中任何一个的多项式复杂度的算法。等等,NPC 又是什么?

在与数不尽的问题搏斗的过程中,人们有时候会发现,解决问题 A
的算法可以同时用来解决问题 B。例如问题 A
是对学生的姓名与所属班级同时排序,问题 B
是对人们按照姓名做排序。这时候,我们只需要让班级全都相同,便能照搬问题 A
的算法来解决问题 B。这种情况下,数学家就说,问题 B 能归约为问题 A。

人们发现,不同的 NP
问题之间也会出现可归约的关系,甚至存在这么一类(不只是一个)问题,使得任何其它的
NP
问题都能归约到它们上。也就是说,能够解决它们的算法就能够解决所有其它的
NP 问题。这一类问题就是 NPC
问题。这样的问题人们已经找到了几千个,如果我们给其中任何一个找到了多项式级别的算法,就相当于证明了
P=NP。但是人们至今没有成功找到,所以大家对 P=NP 的信心大打折扣。

图片 3

 

解密无遮拦?

图片 4《基本演绎法》S02E02
截图。

虽然前景很不乐观,但是不妨来假想一下,如果
P=NP,《基本演绎法》中所说的“破解密码只是小菜一碟”就会成真了吗?

前面说过,证明 P=NP 的一个主要方法就是,给某一个 NPC
问题找到一个快速算法。但是,也不排除有人给出一个“存在性”而非“构造性”的证明,只是告诉大家存在符合要求的算法,但没法详细描述出来。如果
P=NP
被人以这种方式证明出来了,我们也没法依葫芦画瓢地把这个神奇的算法在电脑上写出来,所以对破解密码仍然没有帮助。

退一步说,假如有人构造出可以运用的多项式算法,以此证明了这个问题。这个算法恐怕也很复杂(毕竟这么难找),它的多项式级别的复杂度也可能会非常慢。假设这个算法的复杂度达到了
O(n10),那我们依然面临着不小的麻烦。即使
n=100,运算时间也会增长到非常巨大的地步。

再退一步,假设人类的运气好到 P=NP 是真的,并且找到了复杂度不超过
O(n3)
的算法。如果到了这一步,我们就会有一个算法,能够很快算出某个帐号的密码。《基本演绎法》里面所想象的可能就要成真了,所有的加密系统都会失去效果——应该说,所有会把密码变成数字信息的系统都会失去效果,因为这个数字串很容易被“金钥匙”计算出来。

除此之外,我们需要担心或期许的事情还有很多:

  • 一大批耳熟能详的游戏,如扫雷、俄罗斯方块、超级玛丽等,人们将为它们编写出高效的AI,使得电脑玩游戏的水平无人能及。
  • 整数规划、旅行商问题等许多运筹学中的难题会被高效地解决,这个方向的研究将提升到前所未有的高度。
  • 蛋白质的折叠问题也是一个 NPC
    问题,新的算法无疑是生物与医学界的一个福音。

Wikipedia上有一个关于NPC问题的列表。如果我们手握解决NPC问题的金钥匙,它们全都能被飞快地解决。

除此之外,P=NP 最令人震撼的成果之一可能是下面这段话:

……(P=NP)会将数学转变为让计算机对任何问题寻找拥有合理长度的证明的学科,因为我们能够在多项式时间内验证一个证明是否正确。这些问题也正好包括千禧年大奖的那些问题。

它出自 NP
完全理论奠基人史提芬·古克的笔下。上面这些只言片语的描述,已经展现出了
P=NP情况下,世界将会出现怎样一副天翻地覆的变化。也正是因为这样的结果实在难以置信,人们普遍倾向于相信
P≠NP。我也希望 P≠NP ,这样至少我的网银相对来说还是挺安全的。

 

如上图,比如告诉你从点0到点5的最短路径是22,要验证的话只需要0->1,加上1->5,13+9=22,时间复杂度是常量O(n),假如从上图的六个点扩大到n个点的话,验证过程所需要的算法时间很杂度也都是O(n)。如果没有告诉你最短路径是多要,要用算法来求解的话,我们可以这样来“猜测”它的解:先求一个总路程不超过
100的方案,假设我们可以依靠极好的运气“猜出”一个路线,使得总长度确实不超过100,那么我们只需要每次猜一条路一共猜n次。接下来我们再找总长度不超过
50 的方案,找不到就将阈值提高到75…… 假设最后找到了总长度为 90
的方案,而找不到总长度小于90的方案。我们最终便在多项式时间O(n^k)内“猜”到了这个旅行商问题的解是一个长度为
90 的路线。
是否有不是NP问题的问题呢?有。就是对于那些验证解都无法在多项式时间复杂度内完成的问题。比如问:一个图中是否不存在Hamilton回路?
从图中的任意一点出发,最终回到起点,路途中经过图中每一个结点当且仅当一次,则成为哈密顿回路。
验证Hamilton回路只需要把给定的路径走一次看是不是只每个结点只经过一次,而验证不存在Hamilton回路则需要把每条路径都走一遍否则不敢说不存在Hamilton回路。
之所以要特别的定义NP问题,就在于我们不会去为那些无法在多项式时间复杂度内验证的问题去在多项式的时间复杂度内求它的解,有点拗口,但是多看几遍应该明白,通俗的讲就是对于一个问题告诉你答案让你去验证都需要很长很长时间,可以相像要用算法去求解的话必定需要更长时间。
那么反过来说,所有的P类问题都是NP问题。也就是说,能多项式地解决一个问题,必然能多项式地验证一个问题的解——既然正解都出来了,验证任意给定的解也只需要比较一下就可以了,大不了再算一次给你看也只需要多项式的时间复杂度。关键是,人们想知道,是否所有的NP问题都是P类问题,也就是说是否所有可以用多项式时间验证的问题,也可以在多项式时间内求解。我们可以用集合的观点来说明。如果把所有P类问题归为一个集合P中,把所有NP问题划进另一个集合NP中,那么,显然有P属于NP。现在,所有对NP问题的研究都集中在一个问题上,即究竟是否有P=NP?通常所谓的“NP问题”,其实就一句话:证明或推翻P=NP。
说到这里什么是P类问题什么是NP类问题就讲完了。可能有一些人还不是很清楚,再用通俗但不是很严谨的表述来总结一下。
P类问题就是指那些计算机比较容易算出答案的问题。
NP类问题就是指那些已知答案以后计算机可以比较容易地验证答案的问题。
接下来要进入的话题是为什么P=NP难证明,觉得枯燥的看到这里已经很好了,起码能分清楚P和NP问题了吧,接下来的内容将比较烧脑。

2、NP(Non-deterministicPolynomial)问题

参考文献

  1. P vs. NP on
    Elementary
  2. 什么是P问题、NP问题和NPC问题
  3. A personal view of average-case
    complexity
  4. P versus NP
    problem

图片 5

      有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出,这时就只能通过间接的“猜算”来得到结果,并且一定可以在多项式时间内猜到这个解。(关键是就是不判定这个问题到底有没有解,而是猜出一个解来证明这个问题是有解的)——所有的P类问题都是NP问题。

相关的果壳网小组

  • 数学午餐会
  • 怎样学高数
  • 数据江湖

我们先来看一副集合示意图,这副图反映的是P=NP或P!=NP时候的两个集合的效果,其中就出现了NP-Hard和NPC两个新的概念。要说明为什么目前为止P是否等于NP还没有结论,不得不先弄清楚NPC和NP-Hard。
在引入NPC之前我们先来学习一个概念-归约。简单地说,一个问题A可以归约为问题B的意思是说,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。举个例子,现在有两个问题:求解一个一元一次方程和求解一个一元二次方程。那么我们说,前者可以归约为后者,因为知道怎么样解一个一元二次方程那么一定能解出一元一次方程,因为一元一次方程是一个二次项系数为零的一元二次方程。“问题A可归约为问题B”,那么很容易理解问题B比问题A难,要解决问题B的时间复杂度也就应该大于或等于解决问题A的时间复杂度。而且归约有一项重要的性质:传递性。如果问题A可归约为问题B,问题B可归约为问题C,则问题A一定可归约为问题C,这应该很容易理解吧。现在再来说一下归约的标准概念:如果能找到这样一个变化法则,对任意一个程序A的输入,都能按这个法则变换成程序B的输入,使两程序的输出相同,那么我们说,问题A可归约为问题B。
从归约的定义中我们看到,一个问题归约为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断归约,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。那么如果把一个NP问题不断地归约上去,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以归约成它,并且这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC问题,也就是NP-完全问题。所以NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以归约到它。
既然所有的NP问题都能归约成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,那么NP也就等于P了。因此,目前NPC问题还没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的算法来解决,那么意思就是如果能够找到一个能用多项式时间复杂度解决的NPC问题就证明了P=NP了。
而说到NP-Hard问题。NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条,就是说所有的NP问题都能归化到它,但它本身并不一定是个NP问题,也就是即使有一天发现了NPC问题的多项式算法,但NP-Hard问题仍然无法用多项式算法解决,因为它不是NP问题,对
于答案的验证都很困难。
下面引用Matrix67文章里的逻辑电路的例子来说明NPC问题。
逻辑电路问题是指的这样一个问题:给定一个逻辑电路,问是否存在一种输入使输出为True。
什么叫做逻辑电路呢?一个逻辑电路由若干个输入,一个输出,若干“逻辑门”和密密麻麻的线组成。看下面一例,不需要解释你马上就明白了。

        例子:

图片 6

     
比方说,我RP很好,在程序中需要枚举时,我可以一猜一个准。现在某人拿到了一个求最短路径的问题,问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图,但怎么也算不出来,于是来问我:你看怎么选条路走得最少?我说,我RP很好,肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线,说就这条吧。那人按我指的这条把权值加起来一看,嘿,神了,路径长度98,比100小。于是答案出来了,存在比100小的路径。别人会问他这题怎么做出来的,他就可以说,因为我找到了一个比100小的解。在这个题中,找一个解很困难,但验证一个解很容易。验证一个解只需要O(n)的时间复杂度,也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么,只要我RP好,猜得准,我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的,不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题,即你猜到了解但是没用,因为你不能在多项式的时间里去验证它。举另外一个经典的例子,它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然,前面所说的Hamilton回路是NP问题,因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样:试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了,因为除非你试过所有的路,否则你不敢断定它“没有Hamilton回路”。

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

 

图片 7

      
人们普遍认为,P=NP不成立,也就是说,多数人相信,存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的,就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题,也即所谓的NPC问题。正是NPC问题的存在,使人们相信P≠NP。

上面这个逻辑电路中,无论输入是什么,输出都是False。我们就说,这个逻辑电路不存在使输出为True的一组输入。
回到上文,给定一个逻辑电路,问是否存在一种输入使输出为True,这即逻辑电路问题。
逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题,并且可以直接证明所有的NP问题都可以归约到它。证明过程相当复杂,其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出(想想计算机内部也不过是一些0和1的运算),因此对于一个NP问题来说,问题转化为了求出满足结果为True的一个输入(即一个可行解)。
类似这样的NPC问题,目前还没有找到在多项式复杂度内可以求解的算法,所以说一旦这样的问题都变得多项式复杂度内可解的话,很多问题都可以通过现有的计算机技术进行求解。就比如电脑下围棋,验证一局棋的结果显然是很简单的,但要保证每局都能赢的话目前的方法需要电脑穷举出所有的可能性,并根据每一步棋的变化搜索出最终达到胜利的下棋路径,目前的计算机性能显然是达不到的。因为围棋的状态空间复杂度达到了10的172方,而围棋的博弈树复杂度达到了10的300次方,光看数字可能不直观,一句话就是围棋的变化多过宇宙的原子数量!
所以对于围棋这样的游戏人工智能如果要战胜人类需要实现下面两个条件中的任何一个:
计算机性能无限强大,可以穷举所有可能性;
研究出新的算法,在不穷举的情况下也能保证赢;
目前 Google 的
AlphaGo所做的只不过是通过优化算法提高穷举效率,同时利用现有的大数据与云计算来提升计算性能而已
。下面一篇文章将更详细的介绍AI是如何下围棋的,敬请期待。

3、NPC(NP-complete)问题

     
如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的
NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC
问题,也就是NP-完全问题。

     
NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信,NPC问题是最复杂的问题。我们可以看到,人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。

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

 

 

4、NP-Hard问题

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

 

 

补充:

归约是将某个计算问题(computational
problem)转换为另一个问题的过程。可用归约法定义某些问题的复杂度类(因转换过程而异)。以直觉观之,“问题A可归约为问题B”,指问题B的答案可用于解决问题A。因此解决A不会难于解决B。

《算法导论》上举了这么一个例子。比如说,现在有两个问题:求解一个一元一次方程和求解一个一元二次方程。那么我们说,前者可以约化为后者,意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题,那么我们能找到一个“规则”,按照这个规则把解一元一次方程程序的输入数据变一下,用在解一元二次方程的程序上,两个程序总能得到一样的结果。这个规则即是:两个方程的对应项系数不变,一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题,两个问题就等价了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章