精华内容
下载资源
问答
  • 算法设计与分析什么是P问题NP问题NPC问题.ppt
  • 一、NP 类不同表述、 二、团问题、 三、P NP 问题 ( P vs NP )、





    一、NP 类不同表述



    NP\rm NP 对应的 确定性图灵机 表述 :

    NP\rm NP 类就是有 多项式时间验证机 的 语言 ( 计算问题 ) 的总体集合 ;

    其中的 多项式时间验证机 是一个 确定性图灵机 , 验证机 ;


    NP\rm NP 对应的 非确定性图灵机 表述 :

    NP\rm NP 概念转化到 非确定性图灵机 中 , 有另外一个等价定义 ;

    如果一个语言属于 NP\rm NP , 指的是有一些 非确定性图灵机 可以在 多项式时间 内解决该问题 ;


    上述两个定义时等价的 ;


    确定性图灵机 多项式时间 内 验证 ,

    等价于 ,

    非确定性图灵机 多项式时间 内 解决 ;





    二、团问题



    现在讨论哪些计算问题在 NP\rm NP 中 ;

    团问题 是一个经典的 NP\rm NP 问题 ;


    是一个无向图 点集子集 , 使得 该点集子集 中 任何两个节点之间都有边相连 ;

    团问题 就是 判定无向图中 , 是否包含有 k\rm k 个节点的 团 ;

    在这里插入图片描述

    上述团问题 , 是 NP\rm NP 问题 ;

    给定一个无向图 , 其中有一个 n\rm n 个节点组成的集合 , 验证该 n\rm n 集合是否是团 ;

    验证的方法就是看这 n\rm n 元集中的节点之间两两之间是否有边相连即可 ;

    验证所花的时间是多项式时间 , 该计算问题在 NP\rm NP 中 ;





    三、P 对 NP 问题 ( P vs NP )



    P\rm PNP\rm NP 问题 是计算机科学中最著名的问题 ;

    该问题直接涉及到对计算实质的理解 , 与密码学密切相关 ;

    目前没有实质性进展 ;


    参考 : 百度百科 - P 对 NP 问题


    PNPEXPTIME=kTIME(2nk)\rm P \subseteq NP \subseteq EXPTIME = \bigcup_k TIME(2^{n^k})

    P\rm PNP\rm NP 的子集 ,

    NP\rm NP 是 指数级 ( exponent\rm exponent ) 时间 ( time\rm time ) 的子集 ,

    非确定性图灵机 , 如果要使用 确定性图灵机 来模仿的话 , 时间复杂度时指数级的 ;

    参考博客 【计算理论】计算复杂性 ( 证明 非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的指数关系 )


    上述 33 个不同的复杂类 , 对应的计算模型是不一致的 ,

    P\rm P 对应的是 确定性单个带子图灵机 ,

    NP\rm NP 对应的是 非确定性的单个带子图灵机 ,

    EXPTIME\rm EXPTIME 对应的是 非确定性的单个带子图灵机 ;

    展开全文
  • 对pnp问题的简单介绍 对pnp问题的简单介绍 对pnp问题的简单介绍
  • P/NP问题

    千次阅读 2014-11-16 09:51:03
    呵呵,虽然本人算法不是特别精通,但是最近花了挺多时间在P/NP问题,而且也想到了一个全新的思路,所以今天写一篇关于这个问题的blog,顺便也巩固一下我自己在这方面的认知,如果大家发现本文有任何问题,请指正。...

    呵呵,虽然本人对算法不是特别精通,但是最近花了挺多时间在P/NP问题,而且也想到了一个全新的思路,所以今天写一篇关于这个问题的blog,顺便也巩固一下我自己在这方面的认知,如果大家发现本文有任何问题,请指正。

    什么是P/NP问题?

    P/NP问题可以被认为说整个计算机科学最核心的问题,也是Clay七大千禧年大奖难题之一,首先将给大家介绍一下P/NP问题的四个最核心的概念:

    1.  
      1. NP:由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成,也就是说,NP问题就是那些计算过程比较繁琐,但验证答案却很容易的问题,比如把整数44427进行因数分解,求解过程可能会很费时,但如果告诉你答案是177×251,简单计算即可验证答案是对的,
      2. P:其包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题,P问题也就是那些计算起来很容易,利用多项式算法很快能解决的问题,比如求若干个数的乘积。
      3. NP完全(Complete):NP完全问题应该是最不可能被化简为P(多项式时间可决定)的决定性问题的集合,而且NP完全问题之间是可以互相转换的,也就意味着只要一个NP完全问题能在多项式时间内解决,那么所有的NP完全问题都能在多项式时间内解决。
      4. NP难(Hard):在计算复杂度理论中,定义那些至少和NP里面最难的问题一样难的问题为HP难,也就是说,NP难的问题最差也是NP完全这个级别,比如寻找国际象棋或围棋最佳走法(在n乘n棋盘上)是指数时间完全的。

     

    而P/NP问题,就是论证P=NP还是P!=NP:如果P!=NP,也就是有些很容易得到验证的问题不容易被轻松地求解,这样我们的基于非常容易被验证的素数算法的密钥系统将保持完全,在影响方面,虽然这个世界本来是就是假设P!=NP,所以不会出现任何大的变化,但是整个证明的过程将会对其它一些问题的解决会有一定的启发作用,并对整个科技的发展有一定的推动;如果P=NP的话,每个答案很容易得到验证的问题也同样可以轻松求解,同时NP完全的问题也能被轻松地解决,而整个世界将会发生巨变,比如,所有的基于密钥的安全系统将失灵;算法的研究可能会转向围棋等NP难问题;数学证明可以完全交给计算机来处理;所有人工智能问题都将得到解决,并且机器人能完美模拟人类的行为。下图为P=NP和P!=NP被证明之后,计算复杂度领域新的概览:

    Complexity Class

    图1. 概览

    如果P!=NP,情况和现在差不多,NP完全和P都是NP的子集,但如果P=NP,P、NP和NP完全是相等,也就意味着所有NP完全的算法都能被快速地解决。

    还有,为了方便介绍下面的,稍微介绍一些属于NP完全的算法,比如,著名的旅行商(Travelling Salesman)问题和哈密顿回路(Hamiltonian cycle)和用于测量布尔组合电路效果的布尔可满足性问题(Boolean Satisfiability Problem,简称SAT),下图一些NP完全问题及证明其为NP完全问题的变换流程图。在流程图中,箭头代表的是从何问题变换成另一问题的过程,要注意的是这张图并不代表这些问题的数学关系,事实上任两个本质为NP完全问题都可以以多项式时间变换,这图仅指示可以让研究者较为简单地变换问题的顺序,最源头的是SAT问题。


    图2. NP完全问题

    HP研究员的论文

     HP Guy

    图3. Vinay Deolalikar

    最近,大家都知道HP研究院Vinay Deolalikar在美国时间8月8号发布一篇希望能证明P!=NP的论文,并在接下来的几天根据读者的反馈做了一定的更新,这里是最新版论文概要,经过了包括陶哲轩、Richard Lipton和Timothy Gowers等多位顶级大师的审阅和在网上的讨论,发现Vinay Deolalikar的论文有一定的瑕疵,离证明P!=NP还有一定的距离,下面是陶哲轩的原话:“Ultimately, it seems that what Deolalikar has really proven is not that P != NP, but rather that pp != ppp,for which we have a simple half-page proof(最终,似乎Deolalikar真正已经证明不是P!=NP,而是只需半张纸就能证明的PP!=PPP)”

    证明逻辑 

    简单而言,他首先利用有限模型理论(finite model theory)中对多项式时间的描述,使用到了Moshe Vardi 和Neil Immerman的一个非常精彩的理论:在排序的结构中,一个关系可以定义为一阶逻辑公式加上最小定点(Least Fixed Point)算子,如果这个算子能在多项式时间内被计算。接着,他直接进攻SAT,希望能通过证明属于NP完全问题也是NP里面最难的问题之一的SAT不可能是P,来证明P!=NP,他的方式是:创建一个能编译SAT的排序结构,假设P=NP的话,为了迎合上面提到的理论,SAT会有特定的结构属性,而这些结构属性却和随机SAT的结构有关。总体来说,这个将有限模型理论和Random SAT模型串联起来的思路还是比较新颖。

    主要问题 

    对于论文的证明,许多人有不同的看法,但有一点非常关键,那就是Neil Immerman在Deolalikar对上面提到那个由他创建的理论的使用方式上面非常有异议。

    我的一些想法

    对于这个问题,我个人也已经有了一整套新的思路,但现在还成熟,计划在年内将paper投递给《中国计算机学会通讯》,是证明P=NP还是P!=NP,这个先保密。最后,和大家聊聊一下情怀,最近听闻美国这个季度的GDP增长为1.6,比较乏力,从这个数据我们可以得出,只要在今后十年我们能出现一家能超越微软/苹果/谷歌并能领导这个科技发展的企业,再加上我们庞大的人口基数,在经济总量上接近美国不是一个梦想,所以在这个巨大的浪潮当中,我觉得我们不应该选择抱怨、放弃或者求稳,而应该选择行动、坚持和冒险,因为挑战越大,风险越大,人生才会更好玩!

     

    参考资料:

    1.  
      1. 惠普实验室数学家破解计算机科学最大难题
      2. 假如P=NP,世界将会怎样?
      3. P vs. NP,我们从过去的一周中学到了什么?
      4. P/NP问题
      5. Hamilton环多项式时间算法的说明
      6. NP完全
      7. Deolalikar P vs NP paper
      8. The P≠NP “Proof” Is One Week Old
      9. NP-hard


    转自:http://blog.csdn.net/ikewu83/article/details/5848924
    展开全文
  • 理解P问题和NP问题

    2019-08-14 00:13:57
    NP-hard:比所有的NP问题都难的问题 NP-complete:满足两点: 是NP hard的问题 是NP问题 最简单的例子: 123,456,789,001是不是质数?对于这个问题,计算机科学家可以用现有算法快速得到答案——123,456,789,001...

    最简单的解释:
    P:算起来很快的问题
    NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对
    NP-hard:比所有的NP问题都难的问题
    NP-complete:满足两点:

    • 是NP hard的问题
    • 是NP问题

    最简单的例子:

    123,456,789,001是不是质数?对于这个问题,计算机科学家可以用现有算法快速得到答案——123,456,789,001不是质数。无论这个数字是否会变得越来越大,算法计算所需资源会一直在可控范围内,不会突破天际。这是P问题。

    那么,新的问题产生了:它的质因子有哪些,除了1和本身,它还能被哪些数整除?通常情况下,我们认为它和上个问题拥有不同的“复杂度”。验证一个数是不是质数很简单,但找出它的所有质因子就很困难。目前,算法还不能在短时间内解决这个问题,除非我们已经有了成熟的量子计算机。这是NP问题,但不是P问题。

    什么是P问题?

    代表:多项式时间复杂性类(Polynomial time)

    简介:所有P问题都能被经典计算机(非量子计算机)轻松解决。

    详细说明:如果一个问题是P问题,那么它必须满足在多项式时间内验证一个算法问题的实例是否有解 ,其中n是输入长度,c是个常数。

    典型问题:

    • 这个数是否是个质数?
    • 两点之间的最短路径是什么?

    研究热点:**P=NP是否成立?**如果成立,它将颠覆计算机科学,并使大多密码学内容在一夜之间失效(当然大多数人还是认为P!=NP)。

    什么是NP问题?

    代表:非定常多项式时间复杂性类(Nondeterministic Polynomial time)

    简介:如果给出了一个解,所有NP问题都能被经典计算机快速验证。

    详细说明:如果一个问题有一个解,且能在多项式时间内证明这是个正解,那么这就是个NP问题。

    典型问题:

    • 分团问题。想象一个带边和点的图形,我们把它当成Facebook的社交网络,一个节点代表一个用户,如果两个用户是朋友关系,那么两个节点通过边连接。一个clique表示整个社交网络中的一个子集,其中所有人都是彼此的朋友。那么也许有人会问:这个社交网络中是否存在20人的clique?50人?100人?找到这样一个clique就是个“NP-完全问题”(NPC),这意味着它具有NP中任何问题的最高复杂度。但是,如果问题是50个节点可不可以形成一个小子集,它给出了潜在答案,那么这个NP问题就很容易被验证。
    • 旅行商问题。有许多城市,每个城市之间都有对应的路程距离,旅行商能不能在不到具体里程数的情况下经过所有城市。

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

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

    什么是NPC?

    规约的概念:

    “A 推导出 B” 等价于 “B可以规约为A”。规约相当于更加抽象化的一个过程。规约具有传递性。如果问题A可约化为问题B,问题B可约化为问题C,则问题A一定可约化为问题C。

    NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。

    • 是一个NP问题

    • 所有的NP问题都可以规约到它。

    证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它(由约化的传递性,则NPC问题定义的第二条也得以满足;至于第一个NPC问题是怎么来的,下文将介绍),这样就可以说它是NPC问题了。

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

    什么是NP-Hard问题?

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

    NPC问题实例

    逻辑电路问题是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此,逻辑电路问题是NPC类问题的“鼻祖”。

    逻辑电路问题是指的这样一个问题:给定一个逻辑电路,问是否存在一种输入使输出为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问题还有许多有趣的东西,有待大家自己进一步的挖掘。

    [外链图片转存失败(img-tgSp8PX3-1565712766517)(assets/1565701234498.png)]

    参考资料:

    https://zhuanlan.zhihu.com/p/43412945

    https://zhuanlan.zhihu.com/p/22497908

    展开全文
  • 如何理解PNP问题

    2020-05-28 22:20:30
    2000 年,美国克莱数学研究所公布了世界七大数学难题,又称千禧年大奖难题,规定每一难题的破解者颁发一百万美元的奖金。其中 PNP 问题被列为这七大数学难题之首,PNP 问题被列为七大世界数学难题之首。

    一、背景

    2000 年,美国克莱数学研究所公布了世界七大数学难题,又称千禧年大奖难题,规定对每一难题的破解者颁发一百万美元的奖金,P与 NP 问题被列为七大世界数学难题之首
    NP 问题是随着计算复杂性理论的产生而出现的. 根据计算复杂性理论,所有科学问题按其解决时间可分为三大类:多项式类、指数类和不可解类。

    二、什么是P和NP问题

    P类问题: 所有可以在多项式时间内求解的判定问题构成P类问题,例如乘法、人名排序。

    判定问题:判断是否有一种能够解决某一类问题的能行算法的研究课题。

    NP类问题: 所有的非确定性多项式时间可解的判定问题构成NP类问题。例如车辆路径规划、TSP 等,NP问题最显著的两个特点:一是分布及每一步的并行性,二是任何NP问题都可以转化为是和否的问题,最根本的是验证多项式。

    非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的,算法的验证阶段是确定性的,它验证猜测阶段给出解的正确性。

    NP问题包括P问题,如果能快速地检验问题,是否代表有快速方法破解问题?
    NP问题

    1. 问题变大时,困难度是怎么增加的;
    2. P代表多项式时间(Polynomial),P类问题中解决问题的步数和时间可以依问题大小用多项式函数表达;NP代表非确定性多项式时间(Non deterministic Polynomial time),重点是多项式时间内做检查,即如果有无限台电脑,可以在同一时间检查所有可能的答案,就可以在多项式时间内找到正确的答案;
    3. NP完全问题:NP中困难的部分,即任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题,如果可以找到解决NP-complete问题的快速程序,就可以解决所有NP问题;
    4. NP-hard:指所有NP问题都能在多项式时间复杂度内归约到的问题。
    5. EXP(指数)类问题,例如下棋的最佳棋路、运算和检查都需要指数时间;Co-NP不容易检查正确答案,但很容易排除错误答案;

    三、理解P和NP问题

    首先,了解图灵机模型(TURing Machine-TM),图灵机可以看做是计算机读或写 0 1 时直接进行工作的不见,实际上它是一个抽象的理想计算模型。在计算的每一时刻,它都处于一个可以用表达式描述的状态,这个表达式里包含了图灵机当前的状态、读写头目前所读的数,读写头即将在目前位置写入的数,以及未来读写头的去向(转移方案)等信息。
    P和NP也可以表述为 1:在确定性图灵机下能用多项式求解的问题就是P类问题,而在非确定性图灵机下能用多项式求解的问题就是NP问题;

    • 确定性图灵机与现实中单CPU的计算机在功能上完全等价,只能进行串行思维,而不能同时并行工作,只存在一种状态转移方案;
    • 非确定性图灵机只是一种理论模型,现实中是不存在的。它具有并行工作的能力,完成一件事,要分若干部进行,每一步有多个可能的选择。
    • 确定性图灵机在每一步只能选择一个目标,若进行下去后不能达到目的,可返回到这一步,再试另外的目标;而对非确定性图灵机而言,它每一步可以同时选择这一步的所有目标,并行的同时计算下去。

    1971 年,库克发现并证明了第一个 NP 完全问题( NPC) ,也就是可满足性问题,即任何 NP 问题都可以在多项式时间内按多项式的规模转化为对可满足性问题的求解。只要可满足性问题具有多项式时间算法,则所有 NP问题都具有多项式时间算法,具有这样特性的 NP 问题,称为 NP 完全问题。从此你只要证明任何一个已知的 NP 完全问题,能在
    多项式内转化到你所论及的问题就足够了,因为多项式转化具有传递性。
    对于某个问题,若任何一个 NP 问题都可在多项式时间内按多项式的规模转化为对该问题的求解,则称该问题为 NP-hard

    显然,若任何一个 NP-hard 问题有多项式时间算法,则所有NP 问题具有多项式时间算法。而 NP 完全问题则是:既是 NP-hard 同时又属于 NP 的问题。

    随着第一个 NP 完全问题的发现和证明,兴起了对这类问题之间的多项式转化研究. 在教科书中通常将这种转化称为归约。注意理解多项式归约必须把握两个关键点2:一是转化本身所需的时间是多项式, 二是转化后对原问题计算规模的扩大,不超出多项式的范围。A 问题归约到 B 问题是指 B 问题更具有普适性,即 B 问题的解决方法相对于 A 问题更具有普适性。
    P 和 NP 属计算机算法,算法问题的核心是复杂的思路,而不是数学理论和公式。:即使证明了 NP = P,也不意味着能得到任意 NP 问题的有效的多项式时间算法。从根本上解决 NP 问题的途径是,或者证明NP 等于 P,从而从理论上找到 NP 问题的多项式时间算法;或者证明 NP 不等于 P,从而,某些 NP 问题永远也不可能有多项式时间算法,以免白费时间精力。


    1. 杜立智,符海东,张鸿,黄远林.P与NP问题研究[J].计算机技术与发展,2013,23(01):37-42. ↩︎

    2. 杜立智,陈和平,符海东.NP完全问题研究及前景剖析[J].武汉工程大学学报,2015,37(10):73-78. ↩︎

    展开全文
  • NP问题:算起来不确定快不快的问题,但是我们可以快速验证这个问题的解。 NP-complete问题:属于NP问题,且属于NP-hard问题。 NP-hard问题:比NP问题都要难的问题。 详细说一下这四个问题: P类问题:存在多项式时间...
  • P问题和NP问题

    千次阅读 2017-09-11 00:30:28
    作者:王宇 ... 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 ...P:算起来很快的问题 ...NP:算起来不一定快,但对于任何答案我们都可以...NP-hard:比所有的NP问题都难的问题 NP-c
  • NP-hard:比所有的NP问题都难的问题; NP-complete:满足两点: 1. 是NP hard的问题 2. 是NP问题 这里的“问题”一般形式化为判定问题,如:三班是否有同学刷知乎。 P: 我能在多项式时间内判定三班是否有同学刷...
  • P问题、NP问题、NPC问题、NP难问题的概念 离入职尚有几天时间,闲来无事,将大家常见却又很容易搞糊涂的几个概念进行整理,希望大家有所帮助。你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了...
  • P问题、NP问题、NPC问题、NP hard问题

    万次阅读 多人点赞 2019-01-17 17:33:13
    图论算法摘要 1. 图的概念 图 一个图(graph) G=(V,E)G=(V,E)G=(V,E) 由顶点(vertex)集 VVV 和边(edge)集 EEE 组成。...如果点(a,b),a,b∈V(a,b),a,b∈V(a,b),a,b∈V是有序的,那么图就是有向的...
  • NP问题 可以在多项式时间内检查解是否合法的问题。 “NP” 代表 “nondeterministic polynomial time” 。 显然有P⊆NPP\subseteq NPP⊆NP 归约 对于两个问题A和B,如果能够在多项式时间内A的输入进行转化,使得...
  • 聊聊P/NP问题

    2010-08-30 09:39:00
    呵呵,虽然本人算法不是特别精通,但是最近花了挺多时间在P/NP问题,而且也想到了一个全新的思路,所以今天写一篇关于这个问题的blog,顺便也巩固一下我自己在这方面的认知,如果大家发现本文有任何问题,请指正。...
  • P问题、NP问题、NPC问题的概念及实例证明

    万次阅读 多人点赞 2016-05-21 16:29:25
    首先解释一下什么是NP问题,什么是NP hard问题,什么是NP完全问题。 * P Problem:这个应该最易理解,就是一个问题可以在Polynominal的时间的得到解决,当然,是对于任意input size。 * NP Problem:对于一类问题,...
  • 不同于前面所有文章中的各个具体的问题和算法,NP完全性是一个很抽象的大概念,其包括但不仅限于标题中提到的P问题、NP问题、NPC问题和NP难问题。这里我简单谈谈我书上的内容和一些例子的理解。 P问题 首先来谈谈P...
  • 本文搬运自什么是P问题、NP问题和NPC问题,作者是Matrix67,本文在原文之上略做修改,加黑了重点的地方, 部分稍难理解的地方做了解释,原文已经讲的非常清楚了,向原作者致敬(作者12年前写这篇文章的时候应该...
  • 如果把所有P类问题归为一个集合P中,把所有 NP问题...现在,所有对NP问题的研究都集中在一个问题上,即究竟是否有P=NP?通常所谓的“NP问题”,其实就一句话:证明或推翻P=NP。   这或许是众多OIer最大的误区之一。
  • PNPNP完全问题

    2017-10-16 19:39:00
    如果一个算法的最差时间效率属于O(p(n)),则该算法可以在多项式的时间内对问题进行求解,其中p(n)是输入规模n的一个多项式函数。 可以在多项式时间内求解的问题是易解的。不能在多项式时间内求解的问题是难解的。 ...
  • 这篇博客主要是解释一下我们平时在算法上用到的复杂度和NP还有P的联系,以及为什么第一反应是P的限制整数分解问题竟然“神奇的”是NP问题,以及由此展开的其它问题的一些分析。基本概念知乎上对P和NP有非常详尽的...
  • 最简单的解释:P:算起来很快的问题NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案不对NP-hard:比所有的NP问题都难的问题NP-complete:满足两点:1. 是NP hard的问题2. 是NP问题 稍微正式的...
  • PNP、NPC 问题解释

    2020-05-10 20:12:36
    P、NP、NPC 问题解释行文目的什么是多项式算法什么是P问题什么是NP问题NP问题P问题的关系NPC问题什么是约化(Reducibility)什么是NPC问题NP-hard问题总结 行文目的 目前网络上(知乎、CSDN等)已经有了很多大佬大神...
  • NP-hard:比所有的NP问题都难的问题 NP-complete:满足两点: 1. 是NP hard的问题 2. 是NP问题 接下来是比较严谨的定义: 问题:对于一个包含由0和1组成的字符串集合S,以某个01字符串x作为输入,要求某个...
  • 为了弄清楚上面的概念以及他们有个基本的了解,所以总结出这篇blog。1.多项式时间复杂度定义:问题需要的时间(复杂度)与问题的规模之间是多项式关系。例如,多项式关系形如O(nk)O(n^k),k为某个常数,n是问题的...
  •  以前我老老实实看过算法导论上关于NP问题的那一节,当时细节都弄得很清楚了,但是时隔2、3年就彻底忘完了,今天看到这篇文章,觉得真正从感性上认识了P问题、NP问题、NPC问题,分享一下。并附上我自己本文的总结...
  • 我们看到一个问题,经常会说:“这个没法做,是一个NP问题”,其实这句话是有问题的,我们并没有搞清楚NP问题和NPC问题,大部分情况下,我们想说的NP问题都是NPC问题,NP问题并不是没法做,NPC才是。最近看到一篇...
  • 关于王垠对P=NP?问题的个人看法

    千次阅读 2013-05-14 22:27:46
    在牛人王垠的博客里看到一篇文章,谈了他对P=NP?问题的看法,原文链接如下http://blog.sina.com.cn/s/blog_5d90e82f0101jiwf.html。窃以为可以这样总结他的观点:1.在实践工作中,指数时间和多项式时间的算法孰优孰...
  • P问题和时间复杂度有关,所以本文只谈时间复杂度。 2.时间复杂度 若排序算法有了解的小伙伴,大多是知道冒泡排序的平均时间复杂度为O(n2n^2n2),按照多项式的定义(形如an⋅xn+an−1⋅xn−1+...+a1⋅x+a0a_n·x^n...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 286
精华内容 114
关键字:

p对np问题