精华内容
下载资源
问答
  • Karp的21个NPC问题论文,找到的文字版,便于谷歌翻译
  • NPC问题

    2019-09-23 09:35:46
    研一是密码学专业开的一门课《计算复杂性理论》,当时对立面的NP,NPC这些概念都挺模糊,后来也是不了了之。现在看一些密码学论文的时候经常遇到这一概念,只能硬着头皮搞清楚。下面把自己的理解写下来,一来加深...

      研一是密码学专业开的一门课《计算复杂性理论》,当时对立面的NP,NPC这些概念都挺模糊,后来也是不了了之。现在看一些密码学论文的时候经常遇到这一概念,只能硬着头皮搞清楚。下面把自己的理解写下来,一来加深记忆和理解,而来为以后做个储备。

      问题分为两种,一种是可以通过明确的公式直接得到答案,比如:1+1=?

                             另一种无法直接通过公式求解,比如:给一个数,求出它的因子。

      对于第二种问题我们求解的途径只能通过猜测验证,例如,我们一个数N的因子的时候,一般方法是猜测因子为a,取a=2,然后验证N是否能被a整除,是,则2是因子,否,则a加1继续验证,直到a取到N-1,找出所有的因子。

      第二种问题就称为非确定性问题。在非确定性问题中,验证一个猜测的步骤在多项式时间内可完成,则称为多项式非确定性问题,即NP问题。在NP问题中,验证每一个猜测所用的时间是指数时间。在NP问题中,存在特定的NP问题,其他所有的NP问题都能在多项式时间内转化为该问题,这个NP问题称为NP完全问题,即NPC。所以如果存在一种算法,能在多项式时间内求出NPC问题的正确答案,那么就能在多项式时间内求出所有的NP问题。目前这种算法还没出现。这就是NP是否等于P的问题(能在多项式时间求解的问题称为P问题)。

    转载于:https://www.cnblogs.com/XD-thinker/p/4141370.html

    展开全文
  • NP问题 我说我RP人品运气)很好肯定能随便给你指条很短的路出来然后我就胡乱画了几条线说就这条吧那人按我指的这条把权值加起来一看嘿神了路径长度98比100小于是答案出来了存在比100小的路径 别人会问他这题怎么做...
  • np完全问题所有实例及其证明,非常好的一个文档
  • P问题、NP问题、NPC问题、NP hard问题

    万次阅读 多人点赞 2019-01-17 17:33:13
    NPC问题既是NP问题的子集,又是NP hard问题的子集,所以NPC问题是NP问题和NP hard问题的交集。 NP hard问题和NPC问题都要求能够在 多项式时间 内 规约 成另外一个问题。这里 规约 的意思是 将一个特殊问题一般化...

    图论算法摘要

    1. 图的概念

    一个(graph) G = ( V , E ) G=(V,E) G=(V,E)顶点(vertex)集 V V V边(edge)集 E E E 组成。
    每一条边就是一个点对 ( a , b ) , a , b ∈ V (a,b),a,b∈V (a,b),a,bV。有时候也把边叫做弧(arc)。

    有向图

    如果点对 ( a , b ) , a , b ∈ V (a,b),a,b∈V (a,b),a,bV是有序的,那么图就是有向的(directed)。即 ( a , b ) (a,b) (a,b) ( b , a ) (b,a) (b,a)指不同的边。即这条边必须从点a指向点b,而不能反过来。
    有向的图称为有向图(digraph)。
    顶点 m m m n n n邻接当且仅当 ( m , n ) ∈ E , m , n ∈ V (m,n)∈E,m,n∈V (m,n)E,m,nV

    无向图

    如果点对 ( a , b ) , a , b ∈ V (a,b),a,b∈V (a,b),a,bV是无序的,那么图就是无向的(directed)。即 ( a , b ) (a,b) (a,b) ( b , a ) (b,a) (b,a)指同一条边。
    无向的图称为无向图(digraph)。

    有时候边还能有第三种成分,称作权(weight)或值(cost)。

    2. P问题、NP问题、不可判定问题

    P问题:能够在多项式时间内可用算法求解的问题
    NP问题:非确定型多项式时间(nondeterministic polynomial-time)问题。
    不可判定问题(undecidable problem):"不可能“解出的问题

    P问题的例子:
    假设图 G = ( V , E ) G=(V,E) G=(V,E)顶点(vertex)集 V V V边(edge)集 E E E 组成。顶点集 V V V存在子集 V s u b V_{sub} Vsub,边集 E E E存在子集 E s u b E_{sub} Esub
    欧拉回路问题:找出一条路径恰好经过 E s u b E_{sub} Esub 每条边一次,计算复杂度为 O ( n ) O(n) O(n)

    NP问题的例子:
    哈密顿圈问题:找出一个简单圈,该圈包含 V s u b V_{sub} Vsub 的每一个顶点;通过图G的每个结点一次,且仅一次的通路(回路),就是哈密顿通路(回路),也称哈密顿圈。存在哈密顿圈的图就是哈密顿图。尚且不知道有线性算法。更进一步地,哈密顿圈问题是NPC问题。

    不可判定问题的例子:
    停机问题:让C编译器能够检查语法错误和所有无限循环

    难度:P问题<NP问题<不可判定问题

    不是所有可判定问题都是NP。例如无哈密顿圈问题不确定是否属于NP。

    3. P问题、NP问题、NPC问题、NP hard问题

    与NP相关的总共有四类问题:P问题、NP问题、NPC问题和NP hard问题,是计算复杂度理论中研究的主要内容之一。

    P问题:Polynomial-time问题,能够在多项式时间内用算法求解的问题 。

    P类问题:所有可以在多项式时间内求解的判定问题构成P类问题。判定问题:判断是否有一种能够解决某一类问题的算法的研究课题。

    NP问题:Nondeterministic polynomial-time问题,指不确定是否存在多项式时间的求解算法,但可以在多项式时间内验证一个猜测解的正确性的问题。

    NP类问题:所有的非确定型多项式时间可解的判定问题构成NP类问题。由于解本身显然提供了验证方法,因此NP类问题包括所有具有多项式时间解的问题。但是,既然验证一个答案比提供一个答案容易得多,而且NP只保证了验证算法具有多项式时间,因此在NP中就会存在不具有多项式时间解法的问题。然而,这样的问题至今未被发现。

    NP=P?猜想

    针对NP问题有一个千年难题,即NP=P?,
    也即是否所有能在多项式时间内验证得出正确解的问题,都是具有多项式时间求解算法的问题?
    至今尚未有定论。

    问题来源:
    在一个周六的晚上,你参加了一个盛大的晚会。由于感到局促不安,你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说,你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟,你就能向那里扫视,并且发现你的主人是正确的。然而,如果没有这样的暗示,你就必须环顾整个大厅,一个个地审视每一个人,看是否有你认识的人。
    生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是,如果某人告诉你,数13,717,421可以写成两个较小的数的乘积,你可能不知道是否应该相信他,但是如果他告诉你他可以因式分解为3607乘上3803,那么你就可以用一个袖珍计算器容易验证这是对的。
    人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们于是就猜想,是否这类问题,存在一个确定性算法,可以在多项式时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想。
    不管我们编写程序是否灵巧,判定一个答案是可以很快利用内部知识来验证,而没有这样的提示而需要花费大量时间来求解,被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文·考克于1971年陈述的。

    NP hard问题:Non-deterministic Polynomial hard problem(NPH)问题,如果所有NP问题可在多项式时间内转化(归约,意思是解决了后者也就相应的解决了前者)成某个问题,则该问题称为NP难问题。

    这里规约的意思是将一个特殊问题一般化,即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题,这个问题具有最高的计算复杂度,如果这个最一般的问题也能有多项式时间求解算法,那么那些特殊的原问题也能有多项式时间求解算法。
    解决了这个NP hard问题,所有NP问题都能够被解决了。

    • NP hard问题不一定是NP问题,有可能是不可判定问题。这时候说明原问题也是不可判定的。c

    NPC问题:Non-deterministic Polynomial complete problem ,如果所有NP问题可在多项式时间内归约成某个NP问题,则该NP问题称为NP完全问题。NPC包含了NP中最难的问题。

    解决了这个NPC问题。所有NP问题都能够被解决了。

    • NPC问题相当广泛,包括来自操作系统(调度和安全)、数据库系统、运筹学、逻辑学、特别是图论等不同领域的问题。
      可满足性问题、哈密顿圈问题、巡回售货员问题、最长路径问题都是NPC问题。 装箱(bin packing)问题、背包(knapsack)问题、图的着色(graph coloring)问题以及团(clique)的问题都是著名的NPC问题。NPC问题相当广泛,包括来自操作系统(调度和安全)、数据库系统、运筹学、逻辑学、特别是图论等不同领域的问题。
    • 背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkel和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。

    你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是,NPC是最难的NP问题。

    总结一下:

    • P问题能够保证存在多项式时间求解算法;NP问题不确定是否存在多项式时间求解算法,但确定存在多项式时间验证算法。
    • P问题是NP问题的子集,因为存在多项式时间求解算法的问题,一定能够在多项式时间内被验证。
    • NP hard问题不一定是NP问题,有可能是不可判定问题。这时候说明原问题也是不可判定的。
    • NPC问题既是NP问题的子集,又是NP hard问题的子集,所以NPC问题是NP问题和NP hard问题的交集。
    • NP hard问题和NPC问题都要求能够在多项式时间规约成另外一个问题。这里规约的意思是将一个特殊问题一般化,即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题,这个问题具有最高的计算复杂度,如果这个最一般的问题也能有多项式时间求解算法,那么那些特殊的原问题也能有多项式时间求解算法。
    • 假设 N P = P NP=P NP=P 猜想不成立,那么计算复杂度的相对关系为(按照由低到高): P &lt; N P &lt; N P C &lt; N P h a r d P &lt; NP &lt; NPC &lt; NP hard P<NP<NPC<NPhard
    • 假设 N P = P NP=P NP=P 猜想成立,那么说明所有存在多项式时间验证算法的问题都存在多项式时间求解算法,而NPC本身属于NP问题,因此NPC也存在多项式时间求解算法,所以 N P C = P NPC=P NPC=P,所以 P = N P = N P C P=NP=NPC P=NP=NPC,属于NP hard问题的一个子集。

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

    目前为止这个问题还“啃不动”。但是,一个总的趋势、一个大方向是有的。人们普遍认为,P=NP不成立,也就是说,多数人相信,存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的,就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题,也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在,使人们相信P≠NP。
    NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。
    NP-Hard放宽了限定条件,它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。"[4]

    • 各种问题的计算复杂度如下图(来自参考资料[1])所示:
      在这里插入图片描述

    最后引用一下资料[3] [总结]算法中的P问题、NP问题、NP完全问题和NP难问题关于这几个问题的解释,因为太形象了,基本不需要修改,所以就直接搬运了:

    "著名的NP类问题:旅行家推销问题(TSP)。即有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的环路,这个环路路径小于a。我们知道这个问题如果单纯的用枚举法来列举的话会有 ( n − 1 ) ! (n-1)! (n1)! 种,已经不是多项式时间的算法了,(注:阶乘算法比多项式的复杂)。那怎么办呢?我们可以用猜的,假设我人品好,猜几次就猜中了一条小于长度a的路径,我画画画画,好的,我得到了一条路径小于a的环路,问题解决了,皆大欢喜。可是,我不可能每次都猜的那么准,也许我要猜完所有种呢?所以我们说,这是一个NP类问题。也就是,我们能在多项式的时间内验证并得出问题的正确解,可是我们却不知道该问题是否存在一个多项式时间的算法,每次都能解决他(注意,这里是不知道,不是不存在)。
    所以这就引出了这类讨论的一个千年问题:是否 NP类问题=P类问题?
    即,是否所有能在多项式时间内验证得出正确解的问题,都是具有多项式时间算法的问题呢?
    太让人震惊了,要是解决了这个问题,那岂不是所有的NP问题都可以通过计算机来解决?
    圣战的结果是,有的存在,有的不存在。=_=
    在这场圣战中,人们还发现了很多的东东,也就是我们接下来要介绍的NPC问题和NPH问题。

    为了证明这个千古难题,科学家想出了很多办法。其中之一就是问题的约化。所谓问题约化就是,可以用问题B的算法来解决A ,我们就说问题A可以约化成问题B。举个例子,一元一次方程的求解,跟二元一次方程的求解,我们知道,只要能求解二元一次方程,那就可以用二元一次方程的解法来求解一元一次方程,只需要将一元一次方程加上y,并附加一个方程y=0就可以将一元一次方程变形为一个二元一次方程,然后用二元一次方程的解法来求解这个方程。注意,这里二元一次方程的解法会比一元一次的复杂。所以我们说,只需要找到解二元一次方程的规则性解法,那就能用这个规则性解法来求解一元一次方程。从这里也可以看出,约化是具有传递性的,如A约化到B,B约化到C,A就可以约化到C,同时不断约化下去,我们会发现一个很惊人的特性,就是他一定会存在一个最大的问题,而我们只需要解决了这个问题,那其下的所有问题也就解决啦!这就是我们所说的NPC问题的概念!!!
    引到NP问题里就是,对于同一类的所有的NP类问题,若他们都可以在多项式时间内约化成最难的一个NP类问题,(我们直观的认为,被约化成的问题应具有比前一个问题更复杂的时间复杂度)当我们针对这个时间复杂度最高的超级NP问题要是能找到他的多项式时间算法的话,那就等于变向的证明了其下的所有问题都是存在多项式算法的,即NP=P!!!!给出NPC问题定义,
    NPC问题:如果所有np问题都能在多项式时间内转化为他,则称该np问题为npc问题(NPC:NP
    complete又叫NP完全问题)
    NPC问题是NP问题的子集。

    当然,很多时候NPC问题是找不到一个多项式时间算法的,更多时候他是一个指数级的算法。

    最后介绍下NPH问题。
    NPH问题:我们又叫NP难问题,他不是一个NP问题,然后所有的NPC问题都可以在多项式时间内转化为他的话,我们就叫他NPH(hard)问题。"

    背景知识:确定性问题 VS 非确定性问题、确定性算法 VS 非确定性算法

    确定型机器 VS 非确定型机器

    • 确定型机器在每个时刻都在执行一条命令,根据这条命令,机器再去实行下一条唯一确定的命令。
    • 非确定型机器对其后的步骤是有选择的,可以自由进行它想要的任意选择。如果这些后面的步骤中有一条导致问题的解,那么它总是选择这个正确的步骤。因此,非确定型机器具有非常好的猜测(优化)能力,例如应用于梯度下降
    • NP中的每一个问题都能够用一台非确定型计算机多项式时间内求解。
    • 计算机的一个形式化模型称作图灵机(Turing machine)。
    • 但是**没有人能够构建一台非确定型计算机,非确定性是非常有用的理论结构,但是并没有人们所想的那么强大。**即使使用非确定性,不可判定问题依然是不可判定的。

    确定性问题 VS 非确定性问题 (including NP问题)

    • 确定性问题:有些计算问题是确定性的,例如加减乘除,只要按照公式推导,按部就班一步步来,就可以得到结果;
    • 非确定性问题:但是,有些问题是无法按部就班直接地计算出来。比如,找大质数的问题。有没有一个公式能推出下一个质数是多少呢?这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。
    • 多项式时间非确定性问题(NP问题):如果这个可以告诉你“猜算”的答案正确与否的验证算法,可以在多项式时间内算出来,就叫做多项式时间非确定性问题(NP问题)
    • 而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。
    • 完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的复杂程度是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。
    • 人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们于是就猜想,是否这类问题存在一个确定性算法,可以在多项式时间内直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想
    • 解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。

    确定性算法 VS 非确定性算法(including NP算法)

    • 确定性算法:求解过程的每一步都是确定的,例如一元二次方程的求根算法,只要传入参数,每一步求解都是确定的,这种算法就叫做确定性算法。
    • 我们知道,生成问题的一个解通常比验证一个猜测解要花费更多的时间。判定一个答案是可以很快利用内部知识来验证,而没有这样的提示而需要花费大量时间来求解。也就是验证很简单,求解很困难。
    • 非确定性算法:非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的,算法的验证阶段是确定性的,它验证猜测阶段给出解的正确性
    • 多项式时间非确定性(NP)算法:设算法A是解一个判定问题Q的非确定性算法,如果A的验证阶段能在多项式时间内完成,则称A是一个多项式时间非确定性(NP)算法

    时间复杂度关系(Big O)

    时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。[4]
    “也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。不管数据有多大,程序处理花的时间始终是那么多的,我们就说这个程序很好,具有 O ( 1 ) O(1) O(1)的时间复杂度,也称常数级复杂度;数据规模变得有多大,花的时间也跟着变得有多长,这个程序的时间复杂度就是 O ( n ) O(n) O(n),比如找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!)的阶乘级复杂度。
    不会存在 ( 2 ∗ n 2 ) (2*n^2) (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 ( l o g ( n ) ) , O ( n a ) O(1),O(log(n)),O(n^a) O(1),O(log(n)),O(na)
    等,我们把它叫做多项式级的复杂度,因为它的规模n出现在底数的位置;另一种是 O ( a n ) O(a^n) O(an) O ( n ! ) O(n!) O(n!)型复杂度,它是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。” [4]

    • 按照计算时间递增的方向: O ( 1 ) &lt; O ( l o g ( n ) ) &lt; O ( l o g c n ) &lt; O ( n ) &lt; O ( n l o g ( n ) ) &lt; O ( n 1.5 ) &lt; O ( n 2 ) &lt; O ( n c ) &lt; O ( c n ) &lt; O ( n ! ) &lt; O ( n n ) O(1)&lt;O(log(n))&lt;O({log}^{c}n)&lt;O(n)&lt;O(nlog(n))&lt;O(n^{1.5})&lt;O(n^2)&lt;O(n^c)&lt;O(c^n)&lt;O(n!)&lt;O(n^n) O(1)<O(log(n))<O(logcn)<O(n)<O(nlog(n))<O(n1.5)<O(n2)<O(nc)<O(cn)<O(n!)<O(nn)
    • 多项式时间: O ( n c ) O(n^c) O(nc)
    • 指数时间:: O ( c n ) O(c^n) O(cn)
    • 很多时候NPC问题是找不到一个多项式时间算法的,更多时候它是一个指数级 O ( c n ) O(c^n) O(cn)的算法。
    • NP hard问题的计算复杂度不止多项式时间 O ( n c ) O(n^c) O(nc),可能是 O ( c n ) 、 O ( n ! ) , 甚 至 是 O ( n n ) O(c^n)、O(n!),甚至是O(n^n) O(cn)O(n!)O(nn)
    • 计算机处理的输入常常不是那么几十个几千个那么一点点,想象一下,当计算机处理的数据达到100万个的时候,时间复杂度为 O ( n 2 ) O(n^2) O(n2) O ( e n ) O(e^n) O(en)的算法,所需的运行次数简直是天壤之别, O ( e n ) O(e^n) O(en)指数级的可能运行好几天都没法完成任务,所以我们才要研究一个问题是否存在多项式时间算法。
    • 我们也只在乎一个问题是否存在多项式算法,因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的

    [1] NP问题、NP难问题(NPH)和NP完全问题(NPC)理解
    [2] 百度百科——NP完全问题
    [3] [总结]算法中的P问题、NP问题、NP完全问题和NP难问题
    [4] 什么是P问题、NP问题和NPC问题

    展开全文
  • 如何证明一个问题是NPC问题步骤(step) 步骤(step) 在进入正题前,我想向大家讲解一下归并(reduction)、P和NP的概念。 期望(Desiderata’):假如我们能够在多项式时间(polynomial-time)内解决问题Y,我们考虑...

    步骤(Step)

    在进入正题前,我想向大家讲解一下归约(reduction)、P和NP的概念。

    期望(Desiderata’):假如我们能够在多项式时间(polynomial-time)内解决问题Y,我们考虑能在当前的基础下解决其他哪些问题呢?

    归约(Reduction):当问题X能够在多项式时间内被归约为问题Y,并且对于任意问题X的样例能够被如下方式解决:
    ·多项式个标准的的算法复杂度计算步骤
    ·多项式次调用解决问题Y的步骤

    标记(Notation):X ≤ P Y. (当碰到这个标记时,通常可以理解为Y比X难,并且Y可以解X)

    推论:
    1)若X ≤ P Y并且Y可以再多项式时间内解决,那么X可以再多项式时间内解决
    2)若X ≤ P Y并且X不可以在多项式时间内解决,那么Y也不能在多项式时间内解决
    3)若X ≤ P Y并且Y≤ P X,记作X ≡ P Y。在这种情况下,X能够在多项式时间内被解决当且仅当Y可以在多项式时间内解决

    P问题
    定义(Definition):一组每一个都拥有多项式算法的决策问题(即回答为是或否)通俗地说就是可以再多项式时间内解决的问题
    NP问题
    定义:一组每一个都存在多项式时间证书的(certifier)的决策问题。通俗地讲,就是在多项式时间可以被证明的问题。
    所以P问题也是NP问题。所谓NPC问题也就是对于任意NP问题,都能够在多项式时间内归约成这个问题。也就是说比所有的NP问题都难(当然也有一样难的)
    目前大多数学者认为NP问题真包含P问题,并且与NP-Hard问题有交集,交集即为NPC问题
    在这里插入图片描述
    Figure 0

    一、证明NP
    首先,对任意NP问题,都能成为NPC问题,但是如果单独给我们一个问题,让我们证明它是NPC问题确实有些困难,所以我们取巧。记这个问题为Y,先证明这个问题是NP问题

    二、构造
    找一个NPC问题,记为X,证明:X ≤ P Y

    三、解的充要性
    证明:X有解当且仅当Y有解

    例子(Example)

    根据难度,我提供两个解题例子供大家参考
    一、
    假如你准备安排这学期的课程并且想要保证,冲突的课程数不超过K。你有了3个输入:C={…},S={…},R={{…},{…},…}。C是一个包含不同课程的集合,S为所有课程可用的时间区间,R为学生的要求,包含了各个学生想要学的课程的集合(比如说有两个人,一个想学A,一个想学B,那么R={{A},{B}})。当两个课程被安排在一样的时间区间上发生冲突(即便有个学生两个都想学),证明这个问题是NPC问题

    1.首先,对于任意的时间安排(作为证书。实际上,大多数证明证书都可以随便选,比如说你朋友的名字,虽然听起来非常离谱)。我们遍历所有学生的要求,并且检查他们的要求是否冲突了,并且数出冲突数目。最后检查总数是否小于K。以上的步骤可以再多项式时间内完成。(强烈建议把每一个步骤分开写,然后写上各自的复杂度)所以这个问题是NP。(证明多项式时间内可解,我们大多数时候都是选择最笨的方法,即遍历,然后证明遍历是多项式时间的)

    2.我们选择三染色问题(3-Color问题。给一张图,用三种颜色给点染色,找一个染色方案,使得任意相邻的两点不同色)作为本题选中的NPC问题。对于任意三染色方案,记这张图为G,我们构造本题下的样例,:让每一个点代表一个课程,构造C;让(u,v)代表一个要求里有u,v的学生,构造R;让我们使用的颜色代表时间间隙,构造S;最后,设K为0

    3.我们证明G为正确的三染色方案,当且仅当(C,S,R,K)为这个题目的正确的解:
    LHS->RHS:若G为正确的三染色方案,那么按照课程的颜色安排他们。因为对于任意边(u,v),u和v会被不同的颜色染色,那么对于每一个学生,他的要求就不会被安排在相同的时间间隙下,这也意味着,这个方案是可行的

    RHS->LHS:如果(C,S,R,K)是这个问题的解,那么将G中的点按照他们的时间间隙染色。因为K=0,那么对于所有学生,他们的要求之间没有冲突。这意味着对于每一条边(u,v),u和v不会被相同的颜色染色。所以这是三染色问题的一个正确染色方案。
    综上,这个问题是NPC问题

    是不是看的有点懵呢?这是我的作业里面比较难的一道题,所以大家不要灰心,下面给大家献上一道简单的题

    二、4-COLOR

    给定一个无向图和四种不同的颜色,我们能够提供一种染色方案,使得相邻的点颜色不同吗?证明4-COLOR问题是NPC问题

    1.假设给定任意一种染色方案,首先将这个方案赋给G(O(|V|),V表示G的顶点数),我们在图中遍历这种方案,每遍历一个点时,判断它是否和它的邻点同色,由于各点的度数至多为|V-1|,所以这一步的复杂度为O(|V-1||V|)。所以这个问题可以在给定证书时多项式时间内解决。

    在这里插入图片描述
    Figure 1
    实际上,有这幅图就够了,但是保险起见,还是为大家解释一下,添加一个点(θ(1)),将这个点赋为第四种颜色(θ(1)),将这个点与G中的点全部相连(θ(|V|)),我们得到一个四染色样例
    3.
    LHS->RHS:若三染色样例为真,那么将新的点v加入G,得到一种四染色方案

    RHS->LHS:若四染色样例为真,那么将v与它和G的连边删去,得到一种三染色。
    以上是我的作业的中文版本,但是作为一个合格的CS专业的学生,我建议大家多看看英文方面材料。我将我的作业的原版本放在下面,供大家参考

    在这里插入图片描述
    Figure 2

    做题经验

    我建议大家在做类似题目和准备考试的时候,多准备几个NPC问题,毕竟虽然所有NP问题都可以归约为NPC问题,但是归约的难度显然是不一样的
    在这里插入图片描述
    Figure 3

    常见的有独立集(independent set)、集合覆盖(set cover)、顶点覆盖、哈密顿路(Hamilton road)、电路可满足性问题(circuit set,最古老的NPC问题)、团问题(clique)、旅行商问题、子集和问题(subset sum)、3-SAT(最经典的NPC问题)、三染色问题(3-C)还有一些其他的blablabla
    在这里插入图片描述
    Figure 4

    在这里插入图片描述
    Figure 5 3-SAT

    分析(Analysis)

    一般来说决策问题(Decision problem)弱于搜索问题(Search problem),而搜索问题弱于最优问题(Optimization problem)。但是这三者并没有无法逾越的界限。下面介绍一个例子
    首先介绍一下顶点覆盖(Vertex cover),给定一个G=(V,E)和一个整数k,G的一个大小为k的顶点覆盖表示存在一个为k个点的子集,对任意G中的一条边,有一个点落在这个子集内部(用点覆盖所有的边)
    在这里插入图片描述
    Figure 6
    如在这个图中,就有一个大小为4的顶点覆盖(白点集)
    回到我想要讲的例子中:对图G

    1)决策问题:是否存在一个小于等于k的顶点覆盖

    2)搜索问题:找一个小于等于k的顶点覆盖

    3)最优问题:找到最小的顶点覆盖

    首先显然地,如果有3)的解,那么2)、1)迎刃而解,如果有2)的解,那么1)有解。下面我们仔细思考这三个问题,也许它们之间的差距并非那么大。
    假如我们能够解1),我们通过如下步骤解2),对于图G,我们拿掉一个点,来看这剩下的图中是否有小于等于k-1的顶点覆盖,由于拿掉的这个点有|V|中选择,故我们可以对于这|V|个子图分别解决上面的问题,重复上面的步骤,可以根据我们拿出的点得到2)的解
    OK,我们已经看到1)与2)的差距并没有那么大了,无非是遍历的问题,我们可以用动态规划解决(注意到先取v_1再取v_2和先取v_2再去v_1是相同的),当然这会在后面介绍。
    现在我们假设知道了2)的解法,想知道3)的解,这个更加简单,只需要取k,k-1…,直到t的时候发现G中不存在小于t的顶点覆盖,那么G的最小顶点覆盖就是t+1,并且可以在取t+1时找到解

    总结(Sum up)

    总之,NPC问题就是很难的问题,但是在证明的时候可以站在前人的肩膀上,用已有的NPC问题来证明,2021结束了,我在2019年许下的愿望之一就是五年内开个博客,这是我的第一篇,由于平时学业很忙,所以只有在假期才能写一点,虽然老师教了NPC问题,但是感觉学得并不是很深,有兴趣的兄弟们可以找点论文和书籍看一下,最后川宝倒了,祭奠一下川宝,呜呜呜
    在这里插入图片描述

    展开全文
  • 你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已经被澄清了。下面的内容都是在讲...

      这或许是众多OIer最大的误区之一。

      你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题,什么是NP问题,什么是NPC问题,你如果不是很感兴趣就可以不看了。接下来你可以看到,把NP问题当成是 NPC问题是一个多大的错误。

      还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。不管数据有多大,程序处理花的时间始终是那么多的,我们就说这个程序很好,具有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)的复杂度。

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

      自然地,人们会想到一个问题:会不会所有的问题都可以找到复杂度为多项式级的算法呢?很遗憾,答案是否定的。有些问题甚至根本不可能找到一个正确的算法来,这称之为“不可解问题”(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├─→┤ └──┘ └─→┤ │
    &
    nbsp;└───┘ │ ┌─→┤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问题还有许多有趣的东西,有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的,至少是不要把概念弄混淆了。

    转载自:http://www.matrix67.com/blog/archives/105#comment-1299877
    学习自用

    展开全文
  • 你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已经被澄清了。下面的内容...
  • 可以认为各个问题的难度是不同的,表现形式为,如果我可以把问题A中的一个实例转化为问题B中的一个实例,然后通过解决问题B间接解决问题A,那么就认为B比A更难。通过对归约过程做出限制可以得到不同类型的归约。
  • AI数学基础之:P、NP、NPC问题

    千次阅读 2021-04-28 09:39:52
    我们在做组合优化的时候需要去解决各种问题,根据问题的复杂度不同可以分为P、NP、NPC问题等。今天给大家来介绍一下这些问题类型。
  • 算法NPC问题

    2013-12-24 17:53:01
    算法中的NPC问题,主要说明NPC问题的概念、解决方法和典型例题
  • 时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。O(n)代表的是计算机解决的问题随着规模的增大时间的增加程度和问题的增加规模是相等的。同理O(n^2)...
  • 算法分析与设计——规约和NPC问题

    千次阅读 2019-10-14 17:12:48
    \quad多项式时间归约:如果问题X和问题Y满足以下两条性质,那么问题X可以在多项式时间归约到问题Y。 问题X可以通过多项式时间的基本运算步骤转换为问题Y; 问题X多项式次调用求解问题Y的算法 记为X≤PYX\le_{P}...
  • 六.NPH问题,NPC问题 七.已经被证明的NPC问题 八.一些具体问题的总结 九.总结 一.前言  在讨论算法的时候,常常会说到这个问题的求解是个P类问题,或者是NP难问题等等,同时最近上课正在做算法分析与设计关于...
  • P问题、NP问题、NPC问题以及NP-hard问题理解与区分
  • 1.现实中的问题(比如:排序问题),存在很多解决办法(即计算机领域的算法),所以需要衡量算法的性能。 一个算法的优劣主要从算法的执行时间(即时间复杂度)和所需要占用的存储空间(即空间复杂度)两个方面衡量。 P类...
  • 本文搬运自什么是P问题、NP问题和NPC问题,作者是Matrix67,本文在原文之上略做修改,加黑了重点的地方, 对部分稍难理解的地方做了解释,原文已经讲的非常清楚了,向原作者致敬(作者12年前写这篇文章的时候应该...
  • N、NP、NPC问题分析

    2021-09-16 21:29:55
    对于一个问题,假如现在某个解,如果能在多项式时间内验证这个解是否为正确解,那么这个问题就是NP问题。 例子: 假设有一个没有重复元素的数组arr = […],现在我们希望找到它的中位数median 排序(O(nlogn))...
  • P问题、NP问题、NPC问题、NP-hard问题详解

    万次阅读 多人点赞 2018-09-19 18:44:24
    要理解P问题、NP问题、NPC问题、NP-hard问题,需要先弄懂几个概念: 什么是多项式时间? 什么是确定性算法?什么是非确定性算法? 什么是规约/约化? 多项式时间(Polynomial time) 什么是时间复杂度? 时间...
  • NPC问题的证明 基础概念 P问题:如果一个判定问题能在多项式的时间内解决,那么这个判定问题就属于P问题 NP问题:对于一个判定问题,如果给定一个可能的解实例(称为“证书”),可以在多项式时间内验证这个解实例...
  • 最近因为要证明np问题,所以找了一系列概念去理解这4个问题。理解的时候看到好多人给出了不同的答案,我下面会借鉴别人的答案来总结出一份对于我自己来说,最容易理解这4个问题的说法。 预备知识了解: 这部分内容...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,178
精华内容 4,071
关键字:

npc问题