精华内容
下载资源
问答
  • P问题、NP问题、NPC问题以及NP-hard问题理解与区分

    这或许是众多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就是一个著名的不可解问题,在我的MSN Space上有过专门的介绍和证明。再比如,输出从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├─→┤ └──┘ └─→┤ │
    └───┘ │ ┌─→┤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问题还有许多有趣的东西,有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的,至少是不要把概念弄混淆了。


    1。有解但无算法的问题:
    比如圆周率Pi的小数点后面是否有连续的100万个0。因为Pi是一个客观存在的实数,所以Pi的值是确定的,因此这个问题的解也是存在的。要么是yes,要么是no,虽然我们不知道他到底是什么,但他是客观存在的,不随时间改变,不随人的认识而改变。但是没有算法可以计算这个问题的答案。当然,可以用一种苯办法来解决这个问题,就是不停地计算Pi的小数点后面的值,如果发现了有连续的100万个0,则这个问题的答案就是yes,但是如果没有发现,我们必须一直计算下去,而且永远无法停止~~,所以这种苯办法根本称不上是算法,因为他不满足算法在有限步内终止的条件。所以这个问题是没有算法的(至少目前认为如此,也许以后可以从数论中找到某种方法来求出小数点后面是否有连续的k个0,或从概率的角度计算Pi的小数点后面的值的分布等等等等)。

    2.无解也无算法的问题:
    例如,给定任意一个命题,是否存在一种算法判断这个命题是真是假?这就是著名的图灵停机问题。如果存在这个算法,那么我们只要找到这个算法就可以一劳永逸了,以后无论拿到什么新的命题,都可以用这个算法来验证一下,立刻就知道该命题是真是假,这样我们就掌握了整个宇宙的终极真理:)。但是图灵已经证明了这样的算法是不存在的,这个问题也是无解的。(证明中主要利用了康托尔对角线删除法,就是用来证明实数和自然数不等势的那种对角线删除法)

    3。可计算与不可计算:
    根据图灵-丘奇论题,:
    1。可计算的问题就是能被图灵机计算的问题;(图灵的定义)
    2。可计算的问题就是使用lamda演算系统可以计算的问题;(丘奇的定义)

    图灵丘奇论题与其说是定理,不如说是算法的定义。因为算法本身就是一个不精确的概念,到底什么是算法,以前一直没有确切的定义。而图灵-丘奇论题则从数学上给出了算法的形式定义。

    图灵说:所有的图灵机能计算的问题都是有算法的(也就是可计算的),所有有算法的问题都可以用图灵机计算。这个论题本身是无法证明的,它就像物理中的光速不变定律一样,是一条自然定律,不能加以逻辑上的证明,只能用实验来检验。而目前来看,图灵命题也和光速不变一样,经得住历史和时间的检验,现在即使发展到了量子计算机,还是没有摆脱图灵机的约束,量子计算机上可计算的问题也是普通的图灵机上可计算的问题,只不过计算效率不同而已。

    不可计算的问题的两个例子前面已经说过了,一个是Pi的例子,另一个是图灵停机问题。

    4。可证明性与不可证明性
    在一个公里系统中,有若干条公里,有一些推导规则,在系统中进行定理的证明,就是从公理出发,利用这些规则推导出新的定理。如果最终能得到我们需要证明的命题,则该命题为真;如果最终得到了和我们需要证明的命题相违背的命题,则我们要证明的命题为假。

    如果把系统中所有的定理看作图中的节点,假如从定理i1,i2,..ik根据系统的规则可以推导出定理j,则从i1,i2,…ik分别连接一条到j的有向边。这样整个公理系统构造成了一个有向图。定理的证明过程事实上是在公理系统中从公理表示的节点出发,构造一颗到达目标命题节点的“证明树”。因而定理的证明就和图论中的路经搜索类似(BTW,这就是定理自动化证明的基本原理)。

    超级天才歌德尔在25岁的时候提出了著名的歌德尔不完备性定理。该定理指出:在任何一个公理化系统中,要么存在着矛盾,这个系统是不完备的。
    所谓存在着矛盾,就是可以证明命题A成立,也可以证明命题A的否命题成立,这就自相矛盾了。
    所谓不完备,是指系统中存在着一些命题,无法证明它成立,也无法证明它不成立。这就好像在一个图中存在着某些孤立点,从基本的公理节点出发永远无法访问到这些孤立点。

    歌德尔在“不完备性定理”的证明过程中构造出了一个无法证明是真是伪的定理。具体说起来比较麻烦,我根据自己的理解将其简化为下述的简单形式:

    命题A = “命题A不成立”

    现在问命题A是否成立。如果命题A成立,则根据命题A的内容,命题A应该不成立;如果命题A不成立,则根据命题A的内容,命题A又应该成立。

    这个例子很不严谨,因为它事实上混淆了语法和语义层次。但我觉得这个例子可以作为歌德尔的例子的一个简化版本。歌德的那个例子要比这个严谨和复杂得多,但实质上是差不多的,也是利用了逻辑中的悖论。

    罗素等人所提倡的解决这种悖论的方法就是给谓词逻辑分层次,从而产生了一阶谓词逻辑、二阶谓词逻辑等。像上面的例子,罗素认为命题A的内容描述了命题A本身的性质,这就超出了命题A所能表达的范围,他认为这样的A不是合法的命题。

    【转自:http://www.matrix67.com/blog/archives/105 http://blog.csdn.net/dongwq/article/details/4305435

    展开全文
  • P问题,NP问题,NP完全问题,NP-hard问题P问题NP问题NPC问题(NP-Complete)多项式规约深入理解NPC问题(NP-Complete)P=NP?第一个NPC问题Circuit Satisfiability(电路满足性问题)NPC问题的证明NP-hard问题常见的...

    P问题

    多项式时间可求解的问题,例如利用分治,贪心算法等能够求解的问题都是P问题。结果是positive的

    NP问题

    多项式时间可验证的问题。即这类问题可以被一个多项式时间的算法验证。

    NPC问题(NP-Complete)

    至今没有多项式时间算法可以解决它,结果是negative的

    为了更好理解NPC问题,引入多项式规约(Polynomial Reductions)的概念

    多项式规约

    • 问题A多项式规约至B,记作A ≤p B (A,B皆视作问题集合)

    • 如果问题A中的任何实例α都可以被转化为B中的一个实例β,且满足以下特征:

       1.这个转化算法为多项式时间算法
       2.α的结果为yes当且仅当β的结果为yes
      
    • 如果问题B是多项式时间可解的,那么问题A也是多项式时间可解的

    • 如果问题A不是多项式时间可解的,那么问题B也不是多项式时间可解的

    用集合来理解,问题A问题B都为集合,那么有:
    在这里插入图片描述
    即B中存在一个子集,使得子集里的实例可与A中实例一一对应。

    用优化性问题与判断性问题来理解:
    优化性问题常常可以简化成判断性问题来求解,下面给出一个简单例子:
    在这里插入图片描述
    可见,判断性问题在经过多项式时间算法后,可以转化成为优化性问题。
    故而可以理解,问题B是更难解决的。 (A ≤p B )

    深入理解NPC问题(NP-Complete)

    有了多项式规约的概念,再次深入理解一遍NP完全问题。给出下面的定义:

    1. A∈NP
    2. 对于任一问题B∈NP, 有B ≤p A

    即,A∈NP问题集合中最难问题的集合(子集)
    那么,NPC={A|A is NP-Complete}

    所以,NPC是NP的子集。

    再考虑一下P问题与NP问题的关系:
    P问题是多项式时间可解的问题,NP问题是多项式时间可验证的问题。
    那么有P⊆NP,多项式时间可解的问题总是多项式时间可验证的,多项式时间可验证的问题就不一定是多项式时间可解的。

    于是有下图的关系:
    在这里插入图片描述

    P=NP?

    P是否等于NP还是未知的

    第一个NPC问题

    我们将计算机看作是可以求解任何问题的,那么将计算机可解决的问题抽象出一类问题,就有任何问题都可以规约成计算机可解决的问题。即,任何问题 ≤p 计算机可解决的问题。

    Circuit Satisfiability(电路满足性问题)

    电路满足性问题是第一个NPC问题,也就是通过与、或、非门,可以实现多个输入(无论是0或1)都能得到一个输出1
    在这里插入图片描述
    有了第一个NPC问题,那么其他NPC问题也就能相应地找出来。

    NPC问题的证明

    若想要证明问题Lnew是一个NP-Complete问题

    1. 证明Lnew∈NP
    2. 选出一个相应的老问题Lknown
    3. 设计一个多项式时间算法使得对于每一个老问题的实例,都能转化成新问题的实例。
    4. 证明老问题的实例结果为yes当且仅当新问题的实例结果为yes

    即,Lknown ≤p Lnew
    那么,可证新问题Lnew是一个NP完全问题。
    注:一定是老问题规约到新问题,才得证新问题为NP完全问题。顺序不能搞反

    NP-hard问题

    在证明过程中,由于第一步证明Lnew∈NP,即新问题是多项式时间可验证的。该步骤很容易证明,若省略的话,则得到的Lnew称为是NP-hard问题。

    常见的NP完全问题

    最大团问题(Clique)、顶点覆盖问题(Vertex-Cover)
    旅行商问题(Traveling-Salesman)、哈密顿回路问题(Hamiltonian-Cycle)
    其中,顶点覆盖问题可由最大团问题规约,旅行商问题可由哈密顿回路问题规约

    展开全文
  • P问题、NP问题、NPC问题、NP难问题的概念P问题、NP问题、NPC问题、NP难问题的概念, 你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人...

    P问题、NP问题、NPC问题、NP难问题的概念

    P问题、NP问题、NPC问题、NP难问题的概念

    转载:from http://blog.sina.com.cn/s/blog_5212bec30100o03y.html

       你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题,什么是NP问题,什么是NPC问题,你如果不是很感兴趣就可以不看了。接下来你可以看到,把NP问题当成是 NPC问题是一个多大的错误。
    
       自然地,人们会想到一个问题:会不会所有的问题都可以找到复杂度为多项式级的算法呢?很遗憾,答案是否定的。有些问题甚至根本不可能找到一个正确的算法来,这称之为“不可解问题”(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├─→┤ └──┘ └─→┤ │
    └───┘ │ ┌─→┤AND ├──→输出
    └────────┘┌→┤ │
    ┌───┐ ┌──┐ │ └──┘
    │ 输入3├─→┤ NOT├─→────┘
    └───┘ └──┘


      这是个较简单的逻辑电路,当输入1、输入2、输入3分别为True、True、False或False、True、False时,输出为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问题

    2019-05-18 14:40:45
    复杂性理论中最具有理论意义的当数NP完全性...所谓“NPC完全性(NP-completeness)”问题是这样一个问题:由于“P=NP是否成立”这个问题难以解决,从NP类的问题中分出复杂性最高的一个子类,把它叫做NP完全类。 ...

    复杂性理论中最具有理论意义的当数NP完全性问题(NPC问题)。所谓“NPC完全性(NP-completeness)”问题是这样一个问题:由于“P=NP是否成立”这个问题难以解决,从NP类的问题中分出复杂性最高的一个子类,把它叫做NP完全类。

    已经证明,任取NP类中的一个问题,再任取NP完全类中的一个问题,则一定存在一个具有多项式时间复杂性的算法,可以把NP类问题转化为NP完全类问题。这就表明,只要能证明NP完全类中有一个问题是属于P类的,也就证明了NP类中的所有问题都是P类的,即证明了P=NP。
    已经被证明的NPC问题有哪些?

    1. 团问题
    每一对顶点之间都有一条边连接起来,这样的结构称为团。求最大团问题是NPC问题。
    2.顶点覆盖问题
    确定某个点后,与这个点相连接的顶点都称为被该顶点覆盖了。求最少个数确定点使整个图都被覆盖问题也是NPC问题。
    3.哈密尔顿回路问题
    找到一条路,将一个图上的所有顶点,不重复的走一遍,再回到起点。也是NPC问题。
    4.旅行商问题
    和哈密尔顿回路问题差不多,就是每条边上增加了一个权值。同样是NPC问题。
    

    如何证明一个问题是否为NPC问题?

    1.首先证明该问题为NP问题,即多项式时间内可验证的。
    2.找到一种NPC问题以及一种多项式时间内的规约算法,将NPC问题规约为待证问题。
    

    另外,把NP类问题的补集视为co-NP,那么是否有co-NP=NP?一般认为有如下关系
    在这里插入图片描述
    何为NP困难问题(NP-hard)?NP-hard定义是这样的:

    1.如果所有NP问题在多项式时间内都能规约到此问题;
    2.但此问题不一定是NP问题。
    

    同时已经证明了,所有的NP类问题都可以多项式规约到任何一个NP-hard问题。正如上文中提到“只要能证明NP完全类中有一个问题是属于P类的,也就证明了NP类中的所有问题都是P类的”。那么,此处也可利用NP-hard与NPC问题的关系将NPC问题进行转换,可很容易验证某个NPC问题的解的正确性。

    综上,在现阶段大多数理论计算机科学家们眼中的P、NP和NPC三者之间的关系是这样的,P和NPC都完全包含在NP内,且P∩NPC=∅。总之,P问题一定是NP问题,NPC问题一定为NP问题,NPC问题也一定为NP-hard问题。但是,NP-hard问题不一定为NPC问题,同样P?=NP也待证明。
    在这里插入图片描述
    通常可以从以下几个方面来寻求解决办法:
    1.动态规划与分支限界方法:对于许多NP完全问题来说,用动态规划和分支限界方法常可以得到较高的解题效率。
    2.概率分析:对于许多NP完全问题,其困难实例出现的概念率很小,因此对这类NP完全问题常可以设计出平均性能很好的算法。
    3.近似算法:通常可以设计出解NP完全问题的多项式时间的近似算法,以近似解来代替最优解。
    4.启发式算法:在用别的方法都不能奏效时,也可以采用启发式算法来解NP完全问题。这类方法根据具体问题的启发式搜索策略来求问题的解,在实际使用时可能很有效,但有时很难说清楚它的道理。

    References:
    [1] 吕国英, 李茹. 算法设计与分析(第3版)[M]. 北京:清华大学出版社, 2015. 40-41
    [2] Thomas H.Cormen, Charles E.Leiserson. 算法导论[M]. 北京:机械工业出版社, 2013. 616-646
    [3] 陈玉福.计算机算法设计与分析讲义,2017

    以下转自知乎:
    作者:王宇
    链接:https://www.zhihu.com/question/27039635/answer/101730260
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    准备写个详细点的,为了避免有基础的看得烦,先简单来说:最简单的解释:P:算起来很快的问题NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对NP-hard:比所有的NP问题都难的问题NP-complete:满足两点: 1. 是NP hard的问题 2. 是NP问题接下来是比较严谨的定义:问题:对于一个包含由0和1组成的字符串集合S,以某个01字符串x作为输入,要求某个图灵机判断x在不在S里面。这里的图灵机可以先想象成平时我们用的计算机,S也可以被看成我们要解决的问题。注意我们的问题非常简单,就是要判断某个字符串x是否在某个集合S里面,下面是定义:P:有一个图灵机在多项式时间内能够判断x是否在S里面NP:有一个图灵机M,如果某个字符串x在S里面,那么存在一个验证字符串u(注意这个u是针对这个x的,而且长度必须是x长度的多项式关系),M以x和u作为输入,能够验证x真的是在S里面。NP-hard:如果某个问题S是NP-hard,那么对于任意一个NP问题,我们都可以把这个NP问题在多项式时间之内转化为S,并且原问题的答案和转化后S的答案是相同的。也就是说只要我们解决了S,那么就解决了所有的NP问题。NP-complete:一个问题既是NP-hard,又在NP里面;也就是说 1. 解决了这个问题我们就解决了所有NP问题 2. 这个问题本身也是个NP问题好,下面先来解释为什么会有人搞出来这么莫名其妙的定义。这真是说来话长。。。如果想要充分理解整个理论的动机,就逃不开理解图灵机。1. 图灵机是什么?想象你只有纸带和一个类似于打字机一样的,能够沿着纸带写0或1的自动写字装置(只能顺着纸带写不能跳跃),并且这个机器也能读在某个位置上的字符是0还是1,现在要求你用这样一套东西去实现一个算法,你会怎么做?observe,这就是计算机发明前数学家们手头的工具。粗略的说,这就是图灵机定义的来源。另外我们还需要这个机器能够记录它之前做了什么事情,比如如果用这个机器算100+111,我们需要把纸带移到个位数,再开始加法,但我们需要及其能够记住 纸带已经到个位数 这件事,这样才能达到自动化,所以这个机器应该能够保存几个状态。这时有个问题:状态的数目可以根据输入变化吗?应该是不可以的,因为如果要机器能够自动执行某个算法,我们不希望换个输入就又要把机器重新制造一遍,这样简直比单独手算每个输入还麻烦,所以状态的数量应该是在造机器的时候就定死的(常数)。好奇的同学可能会问:那么状态数量就一定不能变化吗?答案是:如果变化,就不是一个图灵机模型了;图灵机只是很多种计算模型的一种,之所以它这么出名,是因为现代计算机就是一个通用图灵机,我们天天都在用。比如如果我们允许状态的数量根据输入长度变化,那么这就变成了一个boolean circuit,这个具体是什么就不展开了。思考题:能否用上面定义的图灵机来实现一个简单的加法器呢?2. 图灵机为什么这么重要?如上所说,图灵机只是很多种计算模型中的一种。在计算理论之初,很多数学家提出过很多计算模型,图灵证明了其它很多计算模型都等价于图灵机(如果一个问题可以被其他计算模型解决,那么也可以被图灵机解决,反之亦然),时间的差距是多项式级别的(简单的理解为可忽略的差距)如果你做了上面的思考题,那么对图灵机的运作模式应该有一定的感觉了。应该可以隐约感受到:所有的算法都是可以用这样简陋的图灵机实现的。那么问题来了:有没有一个图灵机可以执行所有的算法呢?这个脑洞来源于:图灵机本身无非包含纸袋,状态,字符表(简单的看成0和1),这样一个图灵机当然可以用二进制表示成一串字符,那么我可以构造一个“超级”图灵机N,每当我要计算某个问题S,不但把x输入进去,同时也把某个图灵机M输入进去,这个超级图灵机N就可以根据M的构造模仿M的执行模式,判断x是否在S里面。如果这样一个图灵机存在,那我们就获得了可怕的力量:有一个机器可以执行任意可以用图灵机标识的的算法了(你的电脑就是这样一台机器)!3. 为什么是多项式时间对啊为什么不用指数时间或者常数时间的区别来表示两个计算模型之间的等价呢,尤其是常数时间看起来更自然啊?比如刚才的加法器,如果你试着多增加几个状态,或者不光用01来表示数字,而是用十进制表示数字,你会发现你的计算速度有了多项式时间的提升!在理论体系里面我们不希望这么微小的变化就给我们带来本质上的提升,所以我们用多项式时间定义等价。有的同学可能会问:那很大的多项式怎么办?比如几百次方之类的。。。一般来说常用的多项式算法(也就是P,能够被图灵机在多项式时间内计算),都是低次幂的。然而更合理的解释是:有的算法由于有高次幂,所以就不常用了,比如galactic algorithm,有很好的asymptotic behavior,但因为常数项太大所以从未被使用:Galactic Algorithms实用性和理论研究上确实有不同,理论研究更多的是针对某个计算模型(一般来说就是图灵积)而讲的有效率。4. 关于NP:为什么验证一个答案的正确性这么重要?因为最开始的时候都是数学家在搞这个,对于数学家来说如果有一个机器能帮助他们证明各种定理那就爽了。数学家经常干的两件事:1. 给出证明 2. 验证某个证明是不是对的。直觉上肯定验证更容易一些,但如果somehow可以证明NP=P,也就是说 验证 和 给出证明 其实在数学上是等价的,那么这个证明很可能给出了如何把 验证一个证明是否正确(NP)转化为 如何给出一个证明(P)的方法,从此以后数学家只要思考如何验证证明的正确性就能自动得到证明了,那不爽炸了。那个时候密码学的重要性只是崭露头角,但即使是在数学上的重要性,也足够让这个定义吸引人了。5. 关于NP-complete,为什么要单独把NP里最难的问题拿出来最开始的时候,大家不知道NP的定义是存在所谓 最难的 这么一个东西的,各类问题没有固定的比较标准。搞不好就没有这么一个最难的东西。直到一个叫Cook的数学家做了点CS的工作,最后还悲惨的没拿到教职,用教授的话说:“He’s in the wrong department.” 他证明了任何一个NP形式的问题都可以转换成 3SAT (某个NP问题),3SAT 就是说有n个variable,m个clause,每个clause都是某三个variable 或(|) 在一起, 最后再把所有的clause 和(&) 在一起, 问题是:“有没有一种对于这n个variable的取值可以让整个boolean formula的值为true?” 3SAT 这个问题的优点在于它非常的直观清晰。最开始这篇文章没得到什么重视,直到一个非常出名的计算机科学家Levin看到了这篇文章,突然意识到如果这么多问题都等价于 3SAT 问题,那这就很好地揭示了为什么之前那么多算法问题都找不到快速的(多项式级)算法,因为都和3SAT一样难嘛;另外可以用 3SAT 作为对各种计算问题的分界线,那以后只要发现是NP-complete的问题,大家就不用对于每个问题找解法了。由此衍生了很多对于complexity class的研究,而cook-levin这种把NP问题化为3SAT的思想一次又一次起到了至关重要的作用。6. 常见误区:NP=指数级算法?不是的。NP强调的是:易于验证答案的正确性而指数级算法是指得:存在一个图灵机可以在指数时间内给出答案如果熟悉了NP的定义,会发现明显指数级问题包含NP问题(?)因为根据上面的定义,只要验证对一个输入x是否存在一个u能够被某个图灵机M验证就好了,那么在指数时间内,我们可以定义一个hardcode了所有M的信息的图灵机N,N尝试所有可能的u,看有没有哪个u能迫使M接受x。由于u是多项式长度,这种尝试可以在指数时间内结束。至今为止,我们也只知道NP是包含在指数(EXP)这个class里面的,但不知道它们相不相等。这也是整个复杂度理论很蛋疼的一点:真包含关系极其难以证明。有的时候真的让人很怀疑最初的分类方法是不是合理的,究竟是这些问题就没法被很完美的定义,还是只是我们不够聪明呢?

    作者:uraj
    链接:https://www.zhihu.com/question/27039635/answer/35040172
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    P就是能在多项式时间内解决的问题,NP就是能在多项式时间验证答案正确与否的问题。用大白话讲大概就是这样。所以P是否等于NP实质上就是在问,如果对于一个问题我能在多项式时间内验证其答案的正确性,那么我是否能在多项式时间内解决它?这个表述不太严谨,但通俗来讲就是如此。再说说NP-hardness和NP-completenes. 这里涉及一个概念,不妨称为问题之间的归约。可以认为各个问题的难度是不同的,表现形式为,如果我可以把问题A中的一个实例转化为问题B中的一个实例,然后通过解决问题B间接解决问题A,那么就认为B比A更难。通过对归约过程做出限制可以得到不同类型的归约。复杂度理论里经常用到的规约叫polynomial-time Karp’ reduction。其要求是转化问题的过程必须是多项式时间内可计算的。到这为止NP-hardness和NP-completeness就很好理解了。称问题L是NP-hard,如果任意一个NP的问题都可以多项式规约到L。如果一个NP-hard的问题L本身就是NP的,则称L是NP-complete。这个定义可以推广到所有复杂度类。所以compleness的直观解释就是,我能解决这个问题就相当于具备了用相同级别的计算资源解决这个复杂度类里所有问题的能力。

    展开全文
  • 什么是P问题、NP问题和NPC问题

    千次阅读 2017-04-17 11:48:56
    你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题
  • 研究计算资源中最常见的时间(要通过多少步演算才能解决问题)和空间(在解决问题时需要多少存储器) 归约: 是解决不同算法问题的一种手段。比如有两个算法任务A and B,假如任务A比任务B的复杂性低(简记为A≤B)...
  • P问题、NP问题、NPC问题、NP hard问题

    万次阅读 多人点赞 2019-01-17 17:33:13
    NPC问题:Non-deterministic Polynomial complete problem ,如果所有NP问题可在多项式时间内归约成某个NP问题,则该NP问题称为NP完全问题。NPC包含了NP中最难的问题。 解决了这个NPC问题。所有NP问题都能够被解决...
  • P问题和NP问题

    千次阅读 2018-07-24 11:08:24
    最近在读图解算法,看到P问题和NP问题,分享下书中的知识,加上自己的见解,帮助大家更好的理解P、NP及其他们之间的关系。   首先,我们需要了解概念。 什么是P问题? P是英文单词多项式(Polynomial)的第一个...
  • 经常会遇到“这是NP问题吗?”,“这个只看来只能去搜了“,”这已经被证明是NP问题了”之类的话。但你是否真的知道这几个之间的区别呢?你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。下面的内容都是在...
  •  你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题...
  • P问题、NP问题、NPC问题的概念及实例证明

    万次阅读 多人点赞 2016-05-21 16:29:25
    首先解释一下什么是NP问题,什么是NP hard问题,什么是NP完全问题。 * P Problem:这个应该最易理解,就是一个问题可以在Polynominal的时间的得到解决,当然,是对于任意input size。 * NP Problem:对于一类问题,...
  • NP问题,不可解问题

    千次阅读 2017-01-14 11:53:30
    NP问题概要:NP问题集中研究 P?=NP。现在普遍认为P!=NP。 P问题(polynomial):多项式时间内可以求出解的问题,polynomial中文意思是多项式。信息学竞赛出的问题都是P类问题,因为让你用指数级的时间来搜索答案的问题...
  • 概念P问题:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。...之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。 所有的P类问题都是NP问题。也就
  • 什么是P问题、NP问题和NPC问题 这或许是众多OIer最大的误区之一。 你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题...
  • 什么是P问题、NP问题和NPC问题 这或许是众多OIer最大的误区之一。 你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题...
  • 常见的时间复杂度分为两种级别: 多项式级:O(1) , O(log(n)) , O(n^k); 非多项式级:O(a^n) , O(n!) 当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间...
  • 首先解释一下什么是NP问题,什么是NP hard问题,什么是NP完全问题。 看下面的图,他们之间的关系表示的比较清楚。 P Problem:这个应该最易理解,就是一个问题可以在Polynominal的时间的得到解决,当然,是对于任意...
  • P问题和NP问题

    千次阅读 2017-09-11 00:30:28
    作者:王宇 ... 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 ...NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对...NP-hard:比所有的NP问题都难的问题 NP-c

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,213
精华内容 12,085
关键字:

常见的np问题