精华内容
下载资源
问答
  • 假如老板要你解决一个问题,你绞尽脑汁还是想不出来,叫天天不应,叫地地不灵,这时你走进老板办公室,可以采取3种策略: 1) 一副倒霉像,神情猥琐,可怜巴巴的说:老板,我没做出来,我想我是太蠢了…… boss:...

    先来看一个小故事:(转自:http://zhm2k.blog.163.com/blog/static/5981506820095233143571/

    假如老板要你解决一个问题,你绞尽脑汁还是想不出来,叫天天不应,叫地地不灵,这时你走进老板办公室,可以采取3种策略:

    1)

    一副倒霉像,神情猥琐,可怜巴巴的说:老板,我没做出来,我想我是太蠢了……
    boss:蠢材!滚!
    (失败……)

    2)

    雄赳赳气昂昂跨进老板办公室,大吼一声:小样,你丫给我问题根本就无解,害我白想这么些天,我靠!
    boss:我才靠,自己做不出来就说这个问题无解,要是人人都这样混,我这老板还当个屁阿,滚!
    (做不出来还如此气概,不仅失败,而且欠扁……)

    3)

    从容不迫的说:老板,我做不出来,但是,我敢肯定,那些大牛们也照样做不出来。
    boss:原来是这样,那也难为你了。

    虽然是一个笑话,但也可以为我们的生活研究提供一些思路和指导。当你面对一个问题解决不了时,那么就试图去证明别人也解决不了,这的确是一个偷懒逃避的好借口。我觉得P、NP、NP-complete、NP-hard这些名称的出现,就是因为某些难问题,连大牛们都解决不了,无可奈何之下,只好定义一堆东西,为自己找个理由,免得说自己太笨了。其实这是给出一个面对难解问题的解决思路,如果无法得到最优解,那么先去尝试验证哪些解是不是最优解。

     

    下面依次介绍

    一、计算复杂性

        计算复杂性一般包括时间复杂度和空间复杂度,时间复杂度并不是某算法实际运行需要的时间,而是渐进时间复杂度,即当问题规模趋向于无穷大时,该算法时间复杂度的数量级。常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。这里用大O表示法来表述,给出的是算法的最坏情况的时间代价。

        复杂度关系:c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! 
        其中c是一个常量,如果一个算法的复杂度为c 、 log2N 、n 、 n*log2N ,那么这个算法时间效率比较高,叫做多项式级的复杂度。如果是 2^n , 3^n ,n!,那么稍微大一些的n就会令这个算法不能动了,这些是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

        空间复杂度是指算法在计算机内执行时所需存储空间的度量。这里不再细讲。

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

    二、P问题(Polynomial Solvable)

        定义:那些可以在多项式( polynomial )时间内解决的问题,称为P问题。(或:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。)

        时间复杂度如(n^2, n^4,  n(log(n)))都是多项式时间的,指数级别的如(2^n,n^n)这些就不是多项式时间了。
    三、NP问题(Non-determinstic Polynomial Solvable)

        定义:给定一个解,我们可以在多项式时间内检查他正确与否的决策问题,为NP问题。
    比如,我要找一个图的哈密顿路径,随便给我一个解,我都可以在多项式时间内检查它是不是哈密顿路径。只要形如定义的问题,就是NP问题。

        之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白,信息学中的号称最困难的问题——“NP问题”,实际上是在探讨NP问题与P类问题的关系。

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

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

    四、归约

        为了说明NPC问题,我们先引入一个概念——约化(Reducibility,有的资料上叫“归约”)。

        简单地说,一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。

        “问题A可约化为问题B”有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。

        从约化的定义中我们看到,一个问题约化为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题,联想起约化的传递性,自然地,我们会想问,如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的 NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC 问题,也就是NP-完全问题。

    五、NP-complete问题

        定义:NP-c问题是这样的一类问题,首先他是属于NP的,而且他是NP问题里面最难解决的问题。难到什么程度?只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。
    既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。因此,给NPC找一个多项式算法太不可思议了。

        “正是NPC问题的存在,使人们相信P≠NP”。我们可以就此直观地理解,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。
        NP-c问题的定义出来了,但是,它忽悠了半天,除了说明这类问题比较难之外,其他啥也没有。我们还是不知道到底什么问题是NP-c问题,如何判定一个问题是不是NP-c问题。
        1970年,cook同志发明了cook定理,找到了第一个NP-c问题,SAT(Satisfiability)问题(逻辑电路问题)。他是这么说的,如果SAT问题可以在P时间解决,那么所有的NP问题都可以在P时间内解决。

        有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题,其他还有图染色问题、背包问题等。现在被证明是NPC问题的有很多,任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说,正是因为NPC问题的存在,P=NP变得难以置信。

    六、NP-hard问题
        定义:NP-hard问题是这样的问题,只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。NP-c问题就是NP-hard问题。但注意NP-hard问题它不一定是NP问题,比如,下围棋就是NP-hard问题,但不是NP问题,我们要在一个残局上找一个必胜下法,告诉我们下一步下在哪里。显然,我们找不这个解,而且更难的是,就算有人给我了一个解,我们也无法在P时间内判断它是不是正确的。

    展开全文
  • 什么是NP-Hard

    万次阅读 2018-11-19 14:52:28
    所以首先我想解释一下什么是NP-hard问题 在这之前,必须了解一个概念叫做多项式时间:在计算复杂度理论中,指的是一个问题的计算时间不大于问题大小的多项式倍数,通俗些理解我觉得就是一定规模的问题,总有一个...

    JSP是典型NP-hard问题之一

    所以首先我想解释一下什么是NP-hard问题

    在这之前,必须了解一个概念叫做多项式时间:在计算复杂度理论中,指的是一个问题的计算时间不大于问题大小的多项式倍数,通俗些理解我觉得就是一定规模的问题,总有一个时间范围内可以将它解决,这个范围就是多项式时间

    然后NP是指非确定性多项式(non-deterministic polynomial,缩写NP)。所谓的非确定性是指,可用一定数量的运算去解决多项式时间内可解决的问题。

    再次说下我的理解,NP问题就像是如果给你一个确定那个的例子,你可以很容易的验证他是不是正确,但是如果让你去找这个最优解确实无穷无尽,不太容易求解的

    它躲开了求解到底需要多少时间这样的问题,而仅仅只是强调验证需要多少时间

    再举一个经典的例子

    著名的推销员旅行问题(Travel Saleman Problem or TSP):假设一个推销员需要从香港出发,经过广州,北京,上海,…,等 n 个城市, 最后返回香港。 任意两个城市之间都有飞机直达,但票价不等。假设公司只给报销 C 元钱,问是否存在一个行程安排,使得他能遍历所有城市,而且总的路费小于 C?

    推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排,可以很容易算出旅行总开销。但是,要想知道一条总路费小于 C 的行程是否存在,在最坏情况下,必须检查所有可能的旅行安排! 这将是个天文数字。

    旅行推销员问题是数图论中最著名的问题之一,即“已给一个n个点的完全图,每条边都有一个长度,求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds,Cook和Karp等人发现,这批难题有一个值得注意的性质,对其中一个问题存在有效算法时,每个问题都会有有效算法。

    展开全文
  • P问题NP问题、NPC问题NP-hard问题详解

    万次阅读 多人点赞 2018-09-19 18:44:24
    要理解P问题NP问题、NPC问题NP-hard问题,需要先弄懂几个概念: 什么是多项式时间? 什么是确定性算法?什么是非确定性算法? 什么是规约/约化? 多项式时间(Polynomial time) 什么是时间复杂度? 时间...

    要理解P问题、NP问题、NPC问题、NP-hard问题,需要先弄懂几个概念:

    • 什么是多项式时间?
    • 什么是确定性算法?什么是非确定性算法?
    • 什么是规约/约化?

    多项式时间(Polynomial time)

    什么是时间复杂度?

    时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当程序所处理的问题规模扩大后,程序需要的时间长度对应增长得有多快。也就是说,对于某一个程序,其处理某一个特定数据的效率不能衡量该程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。

    不管数据有多大,程序处理所花的时间始终是那么多的,我们就说这个程序很好,具有 O ( 1 ) O(1) O(1)的时间复杂度,也称常数级复杂度;数据规模变得有多大,花的时间也跟着变得有多长,比如找n个数中的最大值这个程序的时间复杂度就是 O ( n ) O(n) O(n),为线性级复杂度,而像冒泡排序、插入排序等,数据扩大2倍,时间变慢4倍的,时间复杂度是 O ( n 2 ) O(n^2) O(n2),为平方级复杂度。还有一些穷举类的算法,所需时间长度成几何阶数上涨,这就是 O ( a n ) O(a^n) O(an)指数级复杂度,甚至 O ( n ! ) O(n!) O(n!)阶乘级复杂度

    不会存在 O ( 2 ∗ n 2 ) O(2*n^2) O(2n2) 的复杂度,因为前面的那个"2"是系数,根本不会影响到整个程序的时间增长。同样地, O ( n 3 + n 2 ) O(n^3+n^2) O(n3+n2) 的复杂度也就是 O ( n 3 ) O(n^3) O(n3)的复杂度。因此,我们会说,一个 O ( 0.01 ∗ n 3 ) O(0.01*n^3) O(0.01n3)的程序的效率比 O ( 100 ∗ n 2 ) O(100*n^2) O(100n2)的效率低,尽管在n很小的时候,前者优于后者,但后者时间随数据规模增长得慢,最终 O ( n 3 ) O(n^3) O(n3)的复杂度将远远超过 O ( n 2 ) O(n^2) O(n2)。我们也说, O ( n 100 ) O(n^{100}) O(n100)的复杂度小于 O ( 1.0 1 n ) O(1.01^n) O(1.01n)的复杂度。

    容易看出,前面的几类复杂度被分为两种级别,其中后者的复杂度无论如何都远远大于前者。像 O ( 1 ) O(1) O(1), O ( ln ⁡ ( n ) ) O(\ln(n)) O(ln(n)), O ( n a ) O(n^a) O(na)等,我们把它叫做多项式级复杂度,因为它的规模n出现在底数的位置;另一种像是 O ( a n ) O(a^n) O(an) O ( n ! ) O(n!) O(n!)等,它是非多项式级的复杂度,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

    确定性算法与非确定性算法

    确定性算法:

    设A是求解问题B的一个解决算法,在算法的整个执行过程中,每一步都能得到一个确定的解,这样的算法就是确定性算法。

    非确定性算法:

    设A是求解问题B的一个解决算法,它将问题分解成两部分,分别为猜测阶段和验证阶段,其中

    • 猜测阶段:在这个阶段,对问题的一个特定的输入实例x产生一个任意字符串y,在算法的每一次运行时,y的值可能不同,因此,猜测以一种非确定的形式工作。
    • 验证阶段:在这个阶段,用一个确定性算法(有限时间内)验证。①检查在猜测阶段产生的y是否是合适的形式,如果不是,则算法停下来并得到no;② 如果y是合适的形式,则验证它是否是问题的解,如果是,则算法停下来并得到yes,否则算法停下来并得到no。它是验证所猜测的解的正确性。

    规约/约化

    问题A可以约化为问题B,称为“问题A可规约为问题B”,可以理解为问题B的解一定就是问题A的解,因此解决A不会难于解决B。由此可知问题B的时间复杂度一定大于等于问题A。

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

    从规约的定义中我们看到,一个问题规约为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断规约,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC问题,也就是NP-完全问题。

    P类问题、NP类问题、NPC问题、NP难问题

    1. P类问题:能在多项式时间内可解的问题。

    2. NP类问题:在多项式时间内“可验证”的问题。也就是说,不能判定这个问题到底有没有解,而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的,而对其某一个解的验证则能够在多项式时间内完成。P类问题属于NP问题,但NP类问题不一定属于P类问题。

    3. NPC问题:存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。其定义要满足2个条件:

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

    P=NP?

    • 此处会再次从不同的角度来讨论P与NP的定义。

    “P=NP?” 通常被认为是计算机科学最重要的问题。在很早的时候,就有个数学家毫不客气的指出,P=NP? 是个愚蠢的问题,并且为了嘲笑它,专门在4月1号写了一篇“论文”,称自己证明了 P=NP。

    首先,我们要搞清楚什么是“P=NP?” 为此,我们必须先了解一下什么是“算法复杂度”。为此,我们又必须先了解什么是“算法”。我们可以简单的把“算法”想象成一台机器,就跟绞肉机似的。我们给它一些“输入”,它就给我们一些“输出”。比如,绞肉机的输入是肉末,输出是肉渣。牛的输入是草,输出是奶。“加法器”的输入是两个整数,输出是这两个整数的和。“算法理论”所讨论的问题,就是如何设计这些机器,让它们更加有效的工作。就像是说如何培育出优质的奶牛,吃进相同数量的草,更快的产出更多的奶。

    世界上的计算问题,都需要“算法”经过一定时间的工作(也叫“计算”),才能得到结果。计算所需要的时间,往往跟“输入”的大小有关系。你的牛吃越是多的草,它就需要越是长时间才能把它们都变成奶。这种草和奶的转换速度,通常被叫做“算法复杂度”。算法复杂度通常被表示为一个函数f(n),其中n是输入的大小。比如,如果我们的算法复杂度为n^2,那么当输入10个东西的时候,它需要100个单元的时间才能完成计算。当输入100 个东西的时候,它需要10000个单元的时间才能完成。当输入1000个数据的时候,它需要1000000个单元的时间。所谓的“P时间”,多项式时间,就是说这个复杂度函数f(n)是一个多项式。
    “P=NP?”中的“P”,就是指所有这些复杂度为多项式的算法的“集合”,也就是“所有”的复杂度为多项式的算法。为了简要的描述以下的内容,我定义一些术语:

    • “f(n)时间算法”=“能够在f(n)时间之内,解决某个问题的算法”

    当f(n)是个多项式(比如 n 2 n^2 n2)的时候,这就是“多项式时间算法”(P时间算法)。当f(n)是个指数函数(比如 2 n 2^n 2n)的时候,这就是“指数时间算法”(EXPTIME算法)。很多人认为NP问题就是需要指数时间的问题,而NP跟EXPTIME,其实是风马牛不相及的。很显然,P不等于EXPTIME,但是P是否等于NP,却没有一个结论。

    现在我来解释一下什么是NP。通常的计算机,都是确定性(deterministic)的。它们在同一个时刻,只有一种行为。如果用程序来表示,那么它们遇到一个条件判断(分支)的时候,只能一次探索其中一条路径。比如:

    if (x == 0) {
        one();
    }
    else {
        two();
    }
    

    在这里,根据x的值是否为零,one()和two()这两个操作,只有一个会发生。然而,有人幻想出来一种机器,叫做“非确定性计算机”(nondeterministic computer),它可以同时运行这程序的两个分支,one()和two()。这有什么用处呢?它的用处就在于,当你不知道x的大小的时候,根据one()和two()是否“运行成功”,你可以推断出x是否为零。这种方式可以同时探索多种可能性。这不是普通的“并行计算”,因为每当遇到一个分支点,非确定性计算机就会产生新的计算单元,用以同时探索这些路径。这机器就像有“分身术”一样。当这种分支点存在于循环(或者递归)里面的时候,它就会反复的产生新的计算单元,新的计算单元又产生更多的计算单元,就跟细胞分裂一样。一般的计算机都没有 这种“超能力”,它们只有固定数目的计算单元。所以他只能先探索一条路径,失败之后,再回过头来探索另外一条。所以,它们似乎要多花一些时间才能得到结果。到这里,基本的概念都有了定义,于是我们可以圆满的给出P和NP的定义。P和NP是这样两个“问题的集合”:

    P = “确定性计算机”能够在“多项式时间”解决的所有问题
    NP = “非确定性计算机”能够在“多项式时间”解决的所有问题
    (注意它们的区别,仅在于“确定性”或者是“非确定性”。)

    “P=NP?”问题的目标,就是想要知道P和NP这两个集合是否相等。为了证明两个集合(A和 B)相等,一般都要证明两个方向:

    1. A 包含 B;
    2. B 包含 A。

    上一个标题中我们已经说过NP包含了P。因为任何一个非确定性机器,都能被当成一个确定性的机器来用。你只要不使用它的“超能力”,在每个分支点只探索一条路径就行。所以“P=NP?”问题的关键,就在于P是否也包含了NP。也就是说,如果只使用确定性计算机,能否在多项式时间之内,解决所有非确定性计算机能在多项式时间内解决的问题。

    我们来细看一下什么是多项式时间(Polynomial time)。我们都知道, n 2 n^2 n2是多项式, n 1000000 n^{1000000} n1000000 也是多项式。多项式与多项式之间,却有天壤之别。把解决问题所需要的时间,用“多项式”这么笼统的概念来描述,其实是非常不准确的做法。在实际的大规模应用中, n 2 n^2 n2的算法都嫌慢。能找到“多项式时间”的算法,根本不能说明任何问题。对此,理论家们喜欢说,就算再大的多项式(比如 n 1000000 n^{1000000} n1000000),也不能和再小的指数函数(比如 1.000 1 n 1.0001^n 1.0001n)相比。因为总是“存在”一个M,当n>M的时候, 1.000 1 n 1.0001^n 1.0001n会超过 n 1000000 n^{1000000} n1000000。可是问题的关键,却不在于M的“存在”,而在于它的“大小”。如果你的输入必须达到天文数字才能让指数函数超过多项式的话,那么还不如就用指数复杂度的算法。所以,“P=NP?”这问题的错误就在于,它并没有针对我们的实际需要,而是首先假设了我们有“无穷大”的输入,有“无穷多”的时间和耐心,可以让多项式时间的算法“最终”得到优势。


    Reference:

    [1] 对于“NP难问题”的理解:http://blog.csdn.net/u010021014/article/details/77839858
    [2] 谈“P=NP?”:http://yinwang0.lofter.com/post/183ec2_4f6312

    展开全文
  • 首先解释一下什么是NP问题什么是NP hard问题什么是NP完全问题。 看下面的图,他们之间的关系表示的比较清楚。 P Problem:这个应该最易理解,就是一个问题可以在Polynominal的时间的得到解决,当然,是对于...

    http://www.cs.pitt.edu/~ztliu/wordpress/2011/05/np-problem/


    首先解释一下什么是NP问题,什么是NP hard问题,什么是NP完全问题。

    看下面的图,他们之间的关系表示的比较清楚。

    P Problem:这个应该最易理解,就是一个问题可以在Polynominal的时间的得到解决,当然,是对于任意input size。

    NP Problem:对于一类问题,我们可能没有一个已知的快速的方法得到问题的答案,但是如果给我们一个candidate answer,我们能够在polynominal的时间内验证这个candidate answer到底是不是我们已知问题的答案,这类问题叫做NP problem。所以很显然 P Problem是NP problem的一个子集。

    NP-hard Problem:对于这一类问题,用一句话概括他们的特征就是“at least as hard as the hardest problems in NP Problem”, 就是NP-hard问题至少和NP问题一样难。

    NP-complete Problem:对于这一类问题,他们满足两个性质,一个就是在polynomial时间内可以验证一个candidate answer是不是真正的解,另一个性质就是我们可以把任何一个NP问题在polynomial的时间内把他的input转化,使之成为一个NP-complete问题。

    所以对于NP-hard问题,我们可以把他们分成两个部分,一部分可以用polynomial的时间验证一个candidate answer是不是真正的answer,这一部分问题组成了NP-complete集合。

    我们经常说的NP=P或者NP!=P,其实就是说目前而言,我们并不知道,是不是对于NP Problem集合里面的所有问题,都能够在Polynomial的时间内解决。当然只里面比较interesting的一点是,如果我们能把NP-complete集合中的任意一个问题在polynomial的时间内解决了,那么所有的NP问题都可以在polynomial的时间内解决。原因,看看上面说的NP-complete的性质就知道了,因为任何一个NP问题都可以在polynomial的时间内把他的input转化,使之成为一个NP-complete问题,所以….

    介绍了上面说的一些定义,来举几个经典的NP-complete的问题。


    Vertex Cover http://en.wikipedia.org/wiki/Vertex_Cover

    Informally来说,就是对于一个图G(V,E),我们在V中选一个subset V’, 使得E中的所有边得两点中的一个点在V’中。 所谓Vertex Cover也就是说V’中的点cover了每一条边(因为每一条边至少有一端是在V’中的啦)给你一个G(V,E)和一个k,问你在整个G中,是否存在一个大小为k的Vertex Cover(Decision Problem)

    Formally, a vertex cover of a graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. The following figure shows examples of vertex covers in two graphs (the set C is marked with red).

    3-CNF-SAT http://en.wikipedia.org/wiki/3SAT#3-satisfiability

    举个例子,

    [latex]

    E = (X_1 \lor \lnot X_2 \lor \lnot X_3) \wedge (X_1 \lor X_2 \lor X_4)

    [/latex]

    每一个括号包括的东西叫一个clause,里面的X1,X2,X3在离散数学里面叫做文字,取值True或者False。每个括号之间是合取,括号里面是析取,这个问题就是,对于这样的一个表达式,是不是能找到一组Xi的值,使得表达式为True。 Given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?

    Integer Linear Programming http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

    当然这个最显而易见了,就是LP中的所有变量都要求是整数了。关于Linear Programming的问题,后面会专门有一篇文章来讲解。O(∩_∩)O~

    下面来看看我们经常会遇到的一些证明问题。

    证明一个问题是NP问题。证明给你一个结果,你能在polynomial的时间内验证他的正确性

    证明一个问题是NP-hard的。对于证明一个问题是NP-hard,我们经常用到的一个technique是归约(reduction),通常用<=这个符号来表示,如P<=Q,这个就表示P is reducible to Q or Q is the reduction from P or P is reduced to Q. P问题可以归约到Q问题。可以把P归约到Q。这里的reduction的符号可以当成是 比较难易程度的小于等于号,意味着问题Q至少和问题P一样难。当我们要证明一个问题是NP-hard的时候,我们通常要做的是找到一个NPC问题(就用这个代替NP-complete问题),把这个NPC问题归约到NP-hard上去,即NPC<=NP-hard。

    证明一个问题是NPC的。要证NPC,我们要分两步走,第一步证明这个问题属于NP,就是验证答案(感觉这句话我都说烂了)。第二步,证明这个问题是NP-hard的。当然这里面第二步是问题的关键,但是第一步也一定要在证明里面提到。

    如何证明一个问题是NP-hard 是以上证明的关键,即如何归约。

    这里我们归约要做的主要步骤就是,

    1.把NPC的input转化到NP-hard的input,即每一个NPC的input,实际上都是一个NP-hard的input。

    2.把NP-hard的output转化到NPC的output上来,说明给我一个NP-hard的output,我就能给你一个NPC的output。

    注意:以上的两个转化都要在polynomial的时间内完成。

    下面举几个例子来证明上面的归约的方法。


    例 用3SAT 证明 Vertex Cover是NP-hard的。即 3SAT <= Vertex Cover

    这个就是表明我们已知3SAT这个问题是NP-complete的,如何把3SAT问题归约到Vertex Cover上。

    首先,我们要建立我们的通过input建立这两个问题的对应。假设我的3SAT是

    [latex]

    E = (X_1 \lor \lnot X_2 \lor \lnot X_3) \wedge (X_1 \lor X_2 \lor X_4)

    [/latex]

    我们按照下面的方法构造我们的Graph,对应每一个个变量Xi,我们构造点 Xi和~Xi,对于每一个clause,我们构造3个点,这3个点直接彼此有边,假设这三个点叫A,B,C。同时我们还要建立A,B,C这三个点和该clause的联系:假设我们的clause是 (X1 V ~X2 V ~X3) 我们就把X1和A连起来,~X2和B连起来,~X3和C连起来。注意,每一个clause有一个全连通的三角,他们共用那6个变量点(X1,~X1,X2,~X2,X3,~X3) 如下图所示。

    要注意的一点是,对于E中的每一个clause,我们都对应图里面的一个三角形(也就是我用矩形圈住的那部分),同时所有的clause共享上面的六个点,也就是2*变量个数 那么多个点是共用的。

    通过这个图,我们也就建立起了3SAT和Vertex Cover之间的联系。通常这个也是此类证明问题中最难和最creative的部分。

    后面就是表述一下如何进行转换的。通常这个是很trival的部分。

    1)假设我有一个解能满足3SAT,那么我就一定能找到相应的解满足Veterx Cover。 如上图,3SAT满足了,必然每一个clause满足,就拿 (X1 V ~X2 V ~X3) 为例,这个式子满足了,必有一个变量为true,它可以是X1或者~X2或者~X3,假设X1为true,这时对应的vertex cover中,我们就选上面6个点中的X1,同时对于下面的三角形中的3个点,我们选除了那个与X1相连的另外两个点。对于每一个clause,我们都可以这样做,同时,我们也cover了这个图中的所有边。也就是我们有了一个满足要求的vertex cover。

    2)假设我有一个解能满足Vertex Cover,那么我就一定能找到相应的解满足3SAT。因为要cover这个图,所以三角形里面至少要cover两个点,上面的一对一对的pair里面也至少要cover一个,所以对于一个size为n+2m的vertex cover(n是变量个数,m是clause的个数),我们一定可以找到一个满足的3SAT,(显然啊,因为每个clause都有一个点和上面的一对一对pair的点相连) (说的好拗口,郁闷。还不清楚的可以看下这个链接http://users.eecs.northwestern.edu/~fortnow/classes/w08/EECS395/lecture11.pdf

    然后,然后,。。。我们就证完了。

    例 用3SAT证明ILP是NP-hard的。即 3SAT <= ILP

    还是首先找映射,这个映射不涉及图的东西,应该比较容易构造和理解。

    还是拿上面那个3SAT的例子说事。对于 每个clause,我们都对应于ILP中的一个constraint,比如 E中有4个变量,X1,X2,X3 和X4, 我们的ILP中也有同样的这4个变量,并且我们要求他们都是只能取0 或 1。对于一个clause,如(X1 V ~X2 V ~X3) ,我们对应的constraint是 “X1 + (1-X2)+(1-X3)>=1”,很显然了,ILP中的变量选0对应于3SAT中的变量选false,ILP中的变量选1对应于3SAT中的变量选true,这样我们就映射好了。

    很显然,这两个问题的input/output的转换trival的不行了。如果一个clause满足了,对应的那个ILP中的constraint肯定也满足了;反之依然。偷个懒~O(∩_∩)O~

    证毕。

    这类NP的证明问题其实还是很有难度的,只能说很锻炼脑子,对于它有没有用,这要看你对“useful”的定义了,仁者见仁,智者见智吧。


    先来看一个小故事:(转自:http://zhm2k.blog.163.com/blog/static/5981506820095233143571/

    假如老板要你解决一个问题,你绞尽脑汁还是想不出来,叫天天不应,叫地地不灵,这时你走进老板办公室,可以采取3种策略:

    1)图1:

    一副倒霉像,神情猥琐,可怜巴巴的说:老板,我没做出来,我想我是太蠢了……
    boss:蠢材!滚!
    (失败……)

    2)图2:

    雄赳赳气昂昂跨进老板办公室,大吼一声:小样,你丫给我问题根本就无解,害我白想这么些天,我靠!
    boss:我才靠,自己做不出来就说这个问题无解,要是人人都这样混,我这老板还当个屁阿,滚!
    (做不出来还如此气概,不仅失败,而且欠扁……)

    3)图3:

    从容不迫的说:老板,我做不出来,但是,我敢肯定,那些大牛们也照样做不出来。
    boss:原来是这样,那也难为你了。

     

    以上三副图虽然是一个笑话,但也可以为我们的生活研究提供一些思路和指导。当你面对一个问题解决不了时,那么就试图去证明别人也解决不了,这的确是一个偷懒逃避的好借口。我觉得P、NP、NP-complete、NP-hard这些名称的出现,就是因为某些难问题,连大牛们都解决不了,无可奈何之下,只好定义一堆东西,为自己找个理由,免得说自己太笨了。其实这是给出一个面对难解问题的解决思路,如果无法得到最优解,那么先去尝试验证哪些解是不是最优解。

     

    下面依次介绍

    一、计算复杂性

        计算复杂性一般包括时间复杂度和空间复杂度,时间复杂度并不是某算法实际运行需要的时间,而是渐进时间复杂度,即当问题规模趋向于无穷大时,该算法时间复杂度的数量级。常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。这里用大O表示法来表述,给出的是算法的最坏情况的时间代价。

        复杂度关系:c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!
        其中c是一个常量,如果一个算法的复杂度为c 、 log2N 、n 、 n*log2N ,那么这个算法时间效率比较高,叫做多项式级的复杂度。如果是 2^n , 3^n ,n!,那么稍微大一些的n就会令这个算法不能动了,这些是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

        空间复杂度是指算法在计算机内执行时所需存储空间的度量。这里不再细讲。

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

    二、P问题(Polynomial Solvable)

    定义:那些可以在多项式( polynomial )时间内解决的问题,称为P问题。(或:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。)

    时间复杂度如(n^2, n^4,  n(log(n)))都是多项式时间的,指数级别的如(2^n,n^n)这些就不是多项式时间了。
    三、NP问题(Non-determinstic Polynomial Solvable)

    定义:给定一个解,我们可以在多项式时间内检查他正确与否的决策问题,为NP问题。
    比如,我要找一个图的哈密顿路径,随便给我一个解,我都可以在多项式时间内检查它是不是哈密顿路径。只要形如定义的问题,就是NP问题。

    之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白,信息学中的号称最困难的问题——“NP问题”,实际上是在探讨NP问题与P类问题的关系。

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

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

    四、归约

    为了说明NPC问题,我们先引入一个概念——约化(Reducibility,有的资料上叫“归约”)。

    简单地说,一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。

    “问题A可约化为问题B”有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。

    从约化的定义中我们看到,一个问题约化为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题,联想起约化的传递性,自然地,我们会想问,如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的 NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC 问题,也就是NP-完全问题。

    五、NP-complete问题

    定义:NP-c问题是这样的一类问题,首先他是属于NP的,而且他是NP问题里面最难解决的问题。难到什么程度?只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。
    既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。因此,给NPC找一个多项式算法太不可思议了。

    “正是NPC问题的存在,使人们相信P≠NP”。我们可以就此直观地理解,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。

    NP-c问题的定义出来了,但是,它忽悠了半天,除了说明这类问题比较难之外,其他啥也没有。我们还是不知道到底什么问题是NP-c问题,如何判定一个问题是不是NP-c问题。
    1970年,cook同志发明了cook定理,找到了第一个NP-c问题,SAT(Satisfiability)问题(逻辑电路问题)。他是这么说的,如果SAT问题可以在P时间解决,那么所有的NP问题都可以在P时间内解决。

    有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题,其他还有图染色问题、背包问题等。现在被证明是NPC问题的有很多,任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说,正是因为NPC问题的存在,P=NP变得难以置信。

    六、NP-hard问题
    定义:NP-hard问题是这样的问题,只要其中某个问题可以在P时间内解决,那么所有的NP问题就都可以在P时间内解决了。NP-c问题就是NP-hard问题。但注意NP-hard问题它不一定是NP问题,比如,下围棋就是NP-hard问题,但不是NP问题,我们要在一个残局上找一个必胜下法,告诉我们下一步下在哪里。显然,我们找不这个解,而且更难的是,就算有人给我了一个解,我们也无法在P时间内判断它是不是正确的。

     

    更详细的,以下转自:http://blog.csdn.net/crfoxzl/article/details/2192957

    NP问题就是指其解的正确性可以在多项式时间内被检查的一类问题。比如说数组求和,得到一个解,这个解对不对呢,显然是可以在多项式时间内验证的。再比如说SAT,如果得到一个解,也是能在多项式时间内验证正确性的。所以SAT和求和等等都是NP问题。然后呢,有一部分NP问题的解已经可以在多项式时间内找到,比如数组求和,这部分问题就是NP中比较简单的一部分,被命名为P类问题。那么P以外的NP问题,就是目前还不能够在多项式时间内求解的问题了。会不会将来某一天,有大牛发明了牛算法,把这些问题都在多项式时间内解决呢?也就是说,会不会所有的NP问题,其实都是P类问题呢,只是人类尚未发现呢?NP=P吗?

    可想而知,证明NP=P的路途是艰难的,因为NP问题实在太多了,要一一找到多项式算法。这时Stephen A. Cook这位大牛出现了,写了一篇The Complexity of Theorem Proving Procedures,提出了一个NP-complete的概念。NPC指的是NP问题中最难的一部分问题,所有的NP问题都能在多项式时间内归约到NPC上。所谓归约是指,若A归约到B,B很容易解决,则A很容易解决。显然,如果有任何一道NPC问题在多项式时间内解决了,那么所有的NP问题就都成了P类问题,NP=P就得到证明了,这极大的简化了证明过程。那么怎样证明一个问题C是NP完全问题呢?首先,要证明C是NP问题,也就是C的解的正确性容易验证;然后要证明有一个NP完全问题B,能够在多项式时间内归约到C。这就要求必须先存在至少一个NPC问题。这时Cook大牛就在1971年证明了NP完全问题的祖先就是SAT。SAT问题是指给定一个包含n个布尔变量的逻辑式,问是否存在一个取值组合,使得该式被满足。Cook证明了SAT是一个NPC问题,如果SAT容易解决,那么所有NP都容易解决。Cook是怎样做到的呢?

    他通过非确定性图灵机做到的。非确定性图灵机是一类特殊的图灵机,这种机器很会猜,只要问题有一个解,它就能够在多项式时间内猜到。Cook证明了,SAT总结了该机器在计算过程中必须满足的所有约束条件,任何一个NP问题在这种机器上的计算过程,都可以描述成一个SAT问题。所以,如果你能有一个解决SAT的好算法,你就能够解决非确定性图灵机的计算问题,因为NP问题在非图机上都是多项式解决的,所以你解决了SAT,就能解决所有NP,因此——SAT是一个NP完全问题。感谢Cook,我们已经有了一个NPC问题,剩下的就好办了,用归约来证明就可以了。目前人们已经发现了成千上万的NPC问题,解决一个,NP=P就得证,可以得千年大奖(我认为还能立刻获得图灵奖)。

    那么肯定有人要问了,那么NP之外,还有一些连验证解都不能多项式解决的问题呢。这部分问题,就算是NP=P,都不一定能多项式解决,被命名为NP-hard问题。NP-hard太难了,怎样找到一个完美的女朋友就是NP-hard问题。一个NP-hard问题,可以被一个NP完全问题归约到,也就是说,如果有一个NP-hard得到解决,那么所有NP也就都得到解决了。



    展开全文
  • NP-hard问题概念理解

    万次阅读 2019-01-20 22:16:59
    在阅读“三维装箱”问题的论文时,接触到NP-hard problem的概念。该博文记录与其相关的一些概念理解。 时间复杂度:指当问题规模扩大后,程序需要的时间的增长程度,而不是表示一个程序运行需要花的时间。 多项式级...
  • 定义为随着问题规模的增大,算法执行时间增长的快慢。它可以用来表示一个算法运行的时间效率。举个例子,冒泡排序的时间复杂度为O(n2)O(n^2)O(n2) ,取其最高次,可以看出,这是一个时间复杂度为多项式的表示方式 1.2...
  • 本文搬运自什么是P问题NP问题和NPC问题,作者是Matrix67,本文在原文之上略做修改,加黑了重点的地方, 对部分稍难理解的地方做了解释,原文已经讲的非常清楚了,向原作者致敬(作者12年前写这篇文章的时候应该...
  • 1.P(polynominal)问题–多项式问题 存在多项式时间算法的...3.NPH(Nondeterminism Polynomial Hard问题NP问题 1.它不一定是一个NP问题 2.其他属于NP问题都可在多项式时间内归约成它。 通俗理解,NP问题
  • P问题NP问题、NPC问题以及NP-hard问题理解与区分
  • 近似算法关于np问题,很经典的一部著作,可以好好研究近似算法关于np问题,很经典的一部著作,可以好好研究近似算法关于np问题,很经典的一部著作,可以好好研究
  • 在了解P问题NP问题,NPC问题以及NP Hard问题之前,我们需要明白多项式级的复杂度和非多项式级的复杂度。时间复杂度是当问题规模扩大后,程序需要的时间长度增长得有多快。有O(1)的时间复杂度,也称常数级复杂度;...
  • P问题NP问题、NPC问题NP hard问题

    万次阅读 多人点赞 2019-01-17 17:33:13
    NPC问题既是NP问题的子集,又是NP hard问题的子集,所以NPC问题NP问题NP hard问题的交集。 NP hard问题和NPC问题都要求能够在 多项式时间 内 规约 成另外一个问题。这里 规约 的意思是 将一个特殊问题一般化...
  • 文章目录NP-hard vs NP-CompleteReductionSAT ProblemReducing SAT to Shortest Clique ProblemReducing SAT to Shortest Tour ProblemA List of NP-CompleteSet Vertex Cover Problem &amp;amp;amp; ...
  • 证明一个问题NP-Hard问题

    千次阅读 2019-11-19 20:18:37
    证明一个问题NP-Hard问题 证明问题A是NP-Hard问题可以分为两步: 1)对问题A给定一个限制条件,得到问题B; 2)证明问题B是NPC问题
  • P问题: 那些可以在多项式时间内解决的问题。 那什么是多项式时间呢?    答曰:时间复杂度如(n^2, n^4, n(log(n)) ) 都是多项式时间,如(2^n, n^n ) 就不是多项式时间 NP问题: ... NP-hard问题:...
  • 总是看到“NP难”或者“NP=P”还有“多项式时间”,这些到底是什么鬼,??今天好好查了一下,按照我自己的理解总结在这里,说实话在这个问题上我感觉百度好像比维基讲得明白些,知乎解释得比百度更清楚…… 下面的...
  • 通俗解释NP,NPC,NP-Hard问题 我们把解决一类问题的方法或过程,称之为算法。而算法有一个很重要的指标就是时间复杂度O。因为我们最终是要通过计算机来执行这些算法的,而计算机的算力再高也终究是个有限值,因此如果...
  • 什么是P问题NP问题和NPC问题 这或许是众多OIer最大的误区之一。 你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实...
  • NP-Hard问题浅谈

    万次阅读 多人点赞 2016-07-17 23:26:44
    看相关算法的paper的时候,经常会出现NP-Hard这个词。...so,咱们就来看看这个NP-Hard问题,怎么用最简单的方式去了解。1.世界七大数学难题之首2000年,美国克莱数学研究所公布了世界七大数学难题,又称千禧年大
  • 1.现实中的问题(比如:排序问题),存在很多解决办法(即计算机领域的算法),所以需要衡量算法的性能。 一个算法的优劣主要从算法的执行时间(即时间复杂度)和所需要占用的存储空间(即空间复杂度)两个方面衡量。 P类...
  • NP-Hard问题及组合最优化问题

    千次阅读 2019-09-21 23:49:19
    在讲NP-Hard问题问题之前,先讲P类问题NP问题P类问题:可以找到一个多项式时间复杂度的算法去解决的问题NP问题:可以在多项式时间复杂度的算法去验证结果正确性的问题;比如随便拿一个结果,可在多项式时间...
  • 算法:NP问题NP完全问题(NPC),NPhard问题

    万次阅读 多人点赞 2016-12-14 22:51:03
    在做计算机算法关于NP完全问题这一章的作业的时候,发现有很多概念理解的不是很透彻,然后就反复看老师的讲义,在网上查阅各种资料,花了很多时间来弄懂这块的内容。发现书上的概念太正式,定义太标准,不容易很快...
  • P,NP, NPC, NP-Hard问题的关系详解

    千次阅读 2019-01-13 18:44:41
    我想试着把p, np, npc, np-hard问题给大家讲清楚了。讲不清楚,你给我留言,砸我招牌砸我店。 在介绍之前,先说一下什么是确定性问题,什么是非确定性问题。 确定性: 比如小学学的加减乘除之类的,你只要按部就班的...
  • 什么是NP问题,NP-complete和NP-hard问题.

    万次阅读 多人点赞 2012-09-04 16:09:03
    什么是NP问题 概念1: 在计算机学科中,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题、推销员旅行问题、(命题表达式)可满足问题这类,至今没有找到多项式时间算法解的一类问题,称之为NP类...
  • NP-hard问题证明

    2021-03-15 21:35:26
    NP-hard问题:所有的非确定性多项式时间可解的判定问题构成NP问题。 证明1:问题A给定限制条件得到一个特例B问题 证明2:问题B是NPC问题 首先必须知道以下概念: 1. P Problem 如果一个问题可以找到一个能在...
  • NP-hard问题证明

    千次阅读 2019-02-23 12:26:07
    NP-hard问题:比NPC更难,通常在多项式时间内无法验证一个解的正确性。几个复杂度的区别可以看NPC介绍。 常见证明 我们要证明一个问题A是NP-hard问题一般可以分为两步: 1) 对问题A给定限制条件得到一个特例B问题 2...
  • 组合优化问题 组合优化是通过数学方法的研究去寻找离散事件的最优编排、分组、排序和筛选等,是运筹学中一个经典且重要的分支。对于一个极小化问题问题描述如下式: minf(x)s.t.g(x)≥0x∈D min\quad f(x) \\ s.t....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,876
精华内容 4,750
关键字:

hard问题什么是np