精华内容
下载资源
问答
  • np
    万次阅读
    2022-08-03 21:23:42

    帮助理解:

    P类问题就是指那些计算机比较容易算出答案的问题。
    NP类问题就是指那些已知答案以后计算机可以比较容易地验证答案的问题。

    1. “假设你参加一个盛大的宴会,想要知道里面有没有认识的人。宴会的主人对你说,你一定认识正站在甜点桌右边角落里的女士小龙女。你立刻扫向那里,发现他说的是对的。而如果他不告诉你这些,你就需要环顾整个大厅,审视过每一个人,然后才知道有没有认识的人。宴会主人的暗示,容易找到这一步就是P,你按照他的提示发现自己认识小龙女,容易检查这一步就是NP。”
    这其实就是:生成问题的一个解,通常比验证一个给定的解,要花费更多时间。比如,如果让你计算世界上所有原子个数的总和,这个问题很困难,甚至无解。但是,如果有人告诉你世界上一共有500个原子,那么你能很快验证他是错的。很容易验证,却不容易求解,这种就是NP类问题。
    P类问题是可以在多项式时间内解决并验证的一类问题;NP类问题是可以多项式时间验证但是不确定能否在多项式时间内解决的一类问题。
    显然,所有P类问题都属于NP类问题,但是无法确定NP是否等于P。

    2.假设你正在为400名大学生组织住宿,但是空间有限只有100名学生能在宿舍里找到位置。更复杂的是还给了你一份不相容学生的名单,并要求在你的最终选择中不要出现这份名单中的任何一对。
    这是计算机科学家称之为NP问题的一个例子,因为很容易检查一个同事提出的一百个学生的给定选择是否令人满意,然而从头开始生成这样一个列表的任务似乎太难了以至于完全不切实际。
    事实上从400名申请者中选择100名学生的方法总数比已知宇宙中的原子数量还要多!这类其答案可以被快速检查,但是通过任何直接的程序需要不可接受长度的时间来解决,比如300年或者更多...
    斯蒂芬·库克和列昂尼德·莱文在1971年独立地提出了P(即容易找到)和NP(即容易检查)问题

    3.P代表了这样一类问题,计算机在解决它们的时候可以有速度非常快的方法。这个速度和计算机硬件无关,仅仅取决于这个解决方法本身的便捷性。

    NP代表了另一类问题,它们有最优解,但是,其中很多问题,计算机在寻求最优解时,没有快速的方法,甚至,只能傻傻的、暴力的、尝试所有可能的组合,然后找到最优解。NP问题中,最难的一类问题,被称为NPC,也就是NP完全问题。

    如果P=NP,则意味着,每一个NP问题都可以转化成P,也就是每一个难题最终可以变成一个简单命题,让计算机可以快速求解。

    如果P≠NP,则意味着,很多NP问题无法简化成P, 也就是计算机只能很傻很暴力的去求解。

    4.换而言之,就是,人类在解决复杂问题的时候是否有捷径?

    说到这里,大家可能还没有意识到如果P=NP的威力。下面,就来给大家展示一下如果人类找到了世界的捷径,也就是找到了P=NP的方法后,世界会成为一个怎样神奇的样子!

    充满捷径的神奇世界

    大家熟知的证券市场,充满了各种信息,它们交互作用,让准确的结果预测变得完全不可能。这是一个典型的混沌系统,如同天气系统、海洋、足球力学系统一样。然而,如果P=NP,计算机一下子变得足够聪明,当获知了所有信息因子后,计算机竟然可以在极其短时间里,作出极其准确的预测了!从今往后,人们将可以准确预测天气、股票、球赛结果...

    大家是不是已经在惧怕人工智能了?是不是已经在担心机器人将统治我们?但是,比起P=NP 的神奇世界,现在的人工智能还是很蠢的。如果P=NP,机器人将比现在聪明更多更多更多。从此以后,人工智能将可以快速的自我优化了!那时候,人类的末日可能真的就来了。

    当P=NP,计算机将很容易找到一个算法,来知道艺术作品是如何直击人类心灵的,于是,计算机能为每个人订制出他最喜爱的音乐、艺术作品。什么,你认为现在的音乐推荐系统已经可以做到?不不不,在那个P=NP的时代,计算机会自我将算法进化到,钻进你的内心,成为你的私人订制作曲家。

    如今,人类虽然掌握有人类基因数据库的数据,但是对其进行数据分析依然是个NP完全问题,这让科学家即便花费极大运算力气能找出致病基因,也难以个体化订制药品。然而,如果计算机科学家们能够解开P=NP,从此以后,计算机将能快速为每一位患者订制出药物,不管是癌症还是其他和基因有关的疾病。而且为你订制的药物,将不会对你产生副作用,而别人使用未必有用。这世间,再无绝症。

    5.P=NP真的可能吗?

    人类至今还没有找到让任何NP问题变成P问题的算法。虽然一些NP问题数学家或者计算机科学家们找到了一些比较快速并且准确率较高的算法,但是,一个能放之四海而皆准的算法依然没有被找到。

    那没有被找到是不是就不存在呢?

    如今,绝大部分计算机科学家认为,P≠NP, 也就是,那个能轻易解开世界所有谜题的解并不存在。

    同样,人们从直觉、哲学和宗教来看,也难以相信,有解开世界上所有问题的一把简单钥匙。因为,如果这样的钥匙真的存在,它大概早已在这个宇宙中存在了。比如,人类可能早已有了万事万物看一遍就会的本领,或是某种生物一生下来就不必为了生存而抗争,因为它们的算法极其优异,可以在任何环境中以最高效的方式生存下来。

    然而,既然人们直觉上相信,这样的宇宙捷径并不存在,但是证明其不存在,可不是一件简单的事情。

    6.证明P≠NP

    任何一个能够证明P≠NP的人,都可以得到百万美金的奖励。这么多年过去,无数的数学家和计算机科学家都努力过,每年都有数以万计的论文寄往委员会,至今,却没有人获得这笔奖金。

    终其原因,正是本文开头提到的石神和汤川的讨论:提出一个猜想(也就是出题)很容易,但要判断其答案是否正确,非常难。人们猜想了P≠NP,却非常难以证明。

    很多人不理解数学家为什么会非要“证明”一个猜想。“证明”一个猜想,有非常重要的意义,比如,在P≠NP这个问题上,一旦能够证明,就意味着,人们不必再花心血去寻找那个超级算法了,因为,逻辑上,它根本不可能存在!

    只是,至今为止,很多试图证明P≠NP的过程都是错误的,人们最常犯的一个错误是,他们提出一些可能让P=NP成立的算法,然后证明这些算法并不可能存在,进而得出P≠NP的结论。然而,这个逻辑最大的错误在于:这些提出的可能的算法不成立,不带表别的算法不成立。其实,在日常生活中,人们也很容易犯这样的逻辑错误:自己做不到,不等于别人做不到,但人们依然经常认为自己做不到的事情别人也做不到。

    7.那么,人们最终可以证明P≠NP吗?

    菲菲最近在一个相关论坛看到一段很有趣的评论:每当有P≠NP的证明出来,委员会都需要用NP的时间来判断这个证明是否正确。也许,要猜想P≠NP是否能被证明,本身就是个NP问题。

    不过,鉴于困扰人类几百年的费马大定理最终终于被证明了,我们依然应当对P≠NP的证明抱有希望。

    另外,说不定,某天真的找到了P=NP的算法?只是,不知这到底是喜是悲呢?人们如今已经在怀念那个没有那么多数据和信息的“慢生活”时代,等宇宙捷径真的被发现了,生命和生活还能如现在这样,充满了悬念、残缺之美吗?

    来源:

    1.P=NP?这世界真有捷径?

    2.千禧年七大难题之 P = NP_心意乱2m的博客-CSDN博客

    3.出大事了?国防科大教授解决了世界级难题?但到现在没人敢说对错

    4.等等

    更多相关内容
  • P问题、NP问题、NP完全问题和NP难问题

    万次阅读 多人点赞 2019-06-12 14:06:30
     NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能约化到它,但是他不一定是一个NP问题...

     

     

    转载出处。 https://blog.csdn.net/qq_21768483/article/details/80430590

    在讲P类问题之前先介绍两个个概念:多项式,时间复杂度。(知道这两概念的可以自动跳过这部分)

    1、多项式:axn-bxn-1+c

    恩....就是长这个样子的,叫x最高次为n的多项式....

    咳咳,别嫌我啰嗦。。有些人说不定还真忘了啥是多项式了。。例如第一次看到的鄙人→_→

    2、时间复杂度

    我们知道在计算机算法求解问题当中,经常用时间复杂度和空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小,这里暂不讨论。时间复杂度则表示这个算法运行得到想要的解所需的计算工作量,他探讨的是当输入值接近无穷时,算法所需工作量的变化快慢程度。

    举个例子:冒泡排序。

    在计算机当中,排序问题是最基础的,将输入按照大小或其他规则排好序,有利于后期运用数据进行其他运算。冒泡排序就是其中的一种排序算法。假设手上现在有n个无序的数,利用冒泡排序对其进行排序,

    ①首先比较第1个数和第2个数,如果后者>前者,就对调他们的位置,否则不变

    ②接着比较第2个数和第3个数,如果后者>前者,就对调他们的位置,否则不变

    ③一直向下比较直到第n-1和第n个数比较完,第一轮结束。(这时候最大的数移动到了第n个数的位置)

     

    ④重复前三步,但是只比较到第n-1个数(将第二大的数移动到第n-1个数位置)

    ⑤持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    举个实例:5,4,3,2,1,对其进行排序,先是比较5跟4变成4,5,3,2,1,第一轮结束后变成43215,可以计算,当对其排序完正好要经过4+3+2+1=10次比较,当然这是最复杂的情况,即完全反序。可以知道对于n个数,至多要经过1+2+...+n-1即(n^2-n)/2次比较才能排好序。这个式子里n的最高次阶是2,可知道当n→∞时,一次性对其比较次数影响很小,所以我们把这个算法的时间复杂度比作:o(n^2)。取其最高次,可以看出,这是一个时间复杂度为多项式的表示方式。

    时间复杂度排序o(1)<o(n)<o(lgn)<o(n^2)<o(n^a)<o(e^n)(a>2,n表示输入的数据个数,o(1)为常数级别)

     

    好了,介绍完上面的概念就可以开始讲关于什么叫P类问题了。以上个例子冒泡排序为例,我们知道了,在排序这个大问题里,是可以找到一种时间复杂度为多项式o(n^2)的算法(如冒泡排序法)来求解排序问题的,所以我们说排序问题是一个有多项式时间算法的问题。

    所以我们称,

    P类问题:存在多项式时间算法的问题。(P:polynominal,多项式)

     

    然后扯个题外话,为什么我们要研究这个?因为计算机处理的输入常常不是那么几十个几千个那么一点点,想象一下,当计算机处理的数据达到100万个的时候,时间复杂度为o(n^2)和o(e^n)的算法,所需的运行次数简直是天壤之别,o(e^n)指数级的可能运行好几天都没法完成任务,所以我们才要研究一个问题是否存在多项式时间算法。而我们也只在乎一个问题是否存在多项式算法,因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的。

     

    好了,接下来我们介绍NP,先给定义,

    NP类问题:能在多项式时间内验证得出一个正确解的问题。(NP:Nondeterministic polynominal,非确定性多项式)

    P类问题是NP问题的子集,因为存在多项式时间解法的问题,总能在多项式时间内验证他。

     

    注意定义,这里是验证。NP类问题,我用个人的俗话理解就是,不知道这个问题是不是存在多项式时间内的算法,所以叫non-deterministic非确定性,但是我们可以在多项式时间内验证并得出这个问题的一个正确解。举个例子,

    著名的NP类问题:旅行家推销问题(TSP)。即有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的环路,这个环路路径小于a。我们知道这个问题如果单纯的用枚举法来列举的话会有(n-1)! 种,已经不是多项式时间的算法了,(注:阶乘算法比多项式的复杂)。那怎么办呢?我们可以用猜的,假设我人品好,猜几次就猜中了一条小于长度a的路径,我画画画画,好的,我得到了一条路径小于a的环路,问题解决了,皆大欢喜。可是,我不可能每次都猜的那么准,也许我要猜完所有种呢?所以我们说,这是一个NP类问题。也就是,我们能在多项式的时间内验证并得出问题的正确解,可是我们却不知道该问题是否存在一个多项式时间的算法,每次都能解决他(注意,这里是不知道,不是不存在)。

    所以这就引出了这类讨论的一个千年问题:是否 NP类问题=P类问题?

    即,是否所有能在多项式时间内验证得出正确解的问题,都是具有多项式时间算法的问题呢?

    太让人震惊了,要是解决了这个问题,那岂不是所有的NP问题都可以通过计算机来解决?

     

    圣战的结果是,有的存在,有的不存在。=_=

    在这场圣战中,人们还发现了很多的东东,也就是我们接下来要介绍的NPC问题(啊喂,我不是游戏NPC)和NPH问题。

    (PS :网络上经常有人说,这不是个NP问题吗,其实很多时候他们说的应该是NPC问题,而不是NP问题)

    为了证明这个千古难题,科学家想出了很多办法。其中之一就是问题的约化。所谓问题约化就是,可以用问题B的算法来解决A ,我们就说问题A可以约化成问题B。举个例子,一元一次方程的求解,跟二元一次方程的求解,我们知道,只要能求解二元一次方程,那就可以用二元一次方程的解法来求解一元一次方程,只需要将一元一次方程加上y,并附加一个方程y=0就可以将一元一次方程变形为一个二元一次方程,然后用二元一次方程的解法来求解这个方程。注意,这里二元一次方程的解法会比一元一次的复杂。所以我们说,只需要找到解二元一次方程的规则性解法,那就能用这个规则性解法来求解一元一次方程。从这里也可以看出,约化是具有传递性的,如A约化到B,B约化到C,A就可以约化到C,同时不断约化下去,我们会发现一个很惊人的特性,就是他一定会存在一个最大的问题,而我们只需要解决了这个问题,那其下的所有问题也就解决啦!这就是我们所说的NPC问题的概念!!!

    引到NP问题里就是,对于同一类的所有的NP类问题,若他们都可以在多项式时间内约化成最难的一个NP类问题,(我们直观的认为,被约化成的问题应具有比前一个问题更复杂的时间复杂度)当我们针对这个时间复杂度最高的超级NP问题要是能找到他的多项式时间算法的话,那就等于变向的证明了其下的所有问题都是存在多项式算法的,即NP=P!!!!给出NPC问题定义。

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

    首先,它得是一个NP问题;

    然后,所有的NP问题都可以约化到它。

    要证明npc问题的思路就是: 

    先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它。

    (4)NP难问题(NP-hard问题):

        NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能约化到它,但是他不一定是一个NP问题。

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

     

    以上四个问题他们之间的关系可以用下图来表示: 
    这里写图片描述

    展开全文
  • 一、NP 完全的定位、 二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]、 三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]





    一、NP 完全的定位



    计算理论中三个重要概念 : P \rm P P , N P \rm NP NP , N P \rm NP NP 完全 ;


    P \rm P P , N P \rm NP NP , N P \rm NP NP 完全 , 三者的相互关系如下 :

    目前 P \rm P P N P \rm NP NP 的是否相等不确定 , 只知道 P ≤ N P \rm P \leq NP PNP ;

    如果 P ≠ N P \rm P \not= NP P=NP , 则有 P < N P \rm P < NP P<NP , 三者关系如下图左边所示 ;

    如果 P = N P \rm P = NP P=NP , 则三者关系如下图右边所示 ;

    在这里插入图片描述






    二、NP 难 问题 ( P = NP ) 仅做参考 [ 潜在错误 ]



    该观点目前认为是错误的 , 不过没有严格的证明 ;


    P = N P \rm P = NP P=NP 情况分析 : 如果 P = N P \rm P = NP P=NP , 则有 P = N P = N P \rm P = NP = NP P=NP=NP-完全 ;


    N P \rm NP NP 难问题就是 满足 N P \rm NP NP 完全问题的第二个条件 , 不满足第一个条件的问题 ,

    N P \rm NP NP 中的任何计算问题 , 难易程度 , 都不会超过当前的 计算问题 B \rm B B , 则称 B \rm B B N P \rm NP NP 难 的 ;

    N P \rm NP NP 难 问题包含了 P = N P = N P \rm P = NP = NP P=NP=NP-完全 这三种问题 ;

    03:03:45





    三、NP 难 问题 ( P ≠ NP ) 目前公认 [ 潜在正确 ]



    该观点目前认为是正确的 , 同样也没有严格的证明 ;


    P ≠ N P \rm P \not= NP P=NP 情况分析 : 如果 P ≠ N P \rm P \not= NP P=NP , 则有

    P < N P \rm P < NP P<NP ,

    N P \rm NP NP 完全 < N P \rm <NP <NP


    N P \rm NP NP 问题 中包含了三种计算问题 :

    P \rm P P 问题

    N P \rm NP NP 完全问题

    其它问题 , 既不属于 P \rm P P 问题 , 又不属于 N P \rm NP NP 完全问题 ;


    图同构问题 , 就属于 其它问题 , 既不属于 P \rm P P 问题 , 又不属于 N P \rm NP NP 完全问题 ;


    N P \rm NP NP 难 问题 , 包含了 N P \rm NP NP 完全问题 , 不包含 P \rm P P 问题 和 N P \rm NP NP 中的其它问题 ;

    在这里插入图片描述

    证明 N P \rm NP NP 完全的意义 :

    如果能够证明 计算问题 A \rm A A N P \rm NP NP 完全的 , N P \rm NP NP 完全问题 与 P \rm P P 问题 不相交 ,

    说明 该 计算问题 A \rm A A 一定没有有效算法 , 只有有效算法才会在 P \rm P P 中 ,

    因为 没有任何有效算法在 是 N P \rm NP NP 完全的 ;


    如果 计算问题 是 N P \rm NP NP 完全的 , 该算法一定不是有效算法 ;

    展开全文
  • 什么是P = NP?问题

    千次阅读 多人点赞 2022-08-06 13:18:47
    相信很多人都看了最近很火的一部剧——“天才基本法",这部剧中提到了一个学术问题P = NP? ,很多人像我一样很快刷完剧,但是依然不清楚N/P问题,但是有很好奇。所以我今天整理出这篇文章带大家认识一下N/P问题。。...


    提示:以下是本篇文章正文内容,Java系列学习将会持续更新

    引言

     今天我们先放松一下,这篇文章并不是Java课程的学习,而是带大家认识一个学术问题。但是请大家放心,这里并不是学术的探讨,因为我也不懂,我只是搜集一些相关的资料带大家了解一下这个问题。更多的是出于满足一下各位的好奇心。。。

    天才基本法

     相信大家应该都知道最近有一部剧非常火——天才基本法,由雷佳音、张子枫、张新成主演的由同名小说改编的电视剧。
    请添加图片描述
     该剧具体讲了什么内容我就不在这里详细说了,相信有好多小伙伴都已经刷完了(反正我已经刷完了,确实不错,值得推荐),没有看的小伙伴也很值得一看。
     我们今天只研究剧中提到的P=NP?问题,芝士世界的老林和裴之共同证明了P=NP完全成立,这也使得芝士世界的计算机、医疗、环保等多个领域得到了跨越式的发展。
     而草莓世界的老林用尽二十多年的时间都没有能够证明,最后也只是在芝士裴之的帮助下证明了图同构是NP类问题的证明,这只是证明P=NP的一个阶段性胜利。。。
     那我们就了解一下究竟P=NP?是个什么样的问题?

    回到目录…

    什么是P/NP问题?

     P/NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一,同时也是计算机科学领域的最大难题,关系到计算机完成一项任务的速度到底有多快。

     P/NP问题是Steve Cook于1971年首次提出。

     P指多项式时间(Polynomial),一个复杂问题如果能在多项式时间内解决,那么它便被称为P问题,这意味着计算机可以在有限时间内完成计算;

     NP指非确定性多项式时间(nondeterministic polynomial),一个复杂问题不能确定在多项式时间内解决。

     假如NP问题能找到算法使其在多项式时间内解决,那说明它转变成了P类问题。

    有点难以理解,那就拿股市举个例子:

     昨天某只股票收盘价为10元,今天收盘价为11元。涨幅是多少?
     我们很容易就可以通过公式计算出来,(11-1)/10=10%,这就是P类问题

     那再请问,明天的收盘价是多少?是涨还是跌?
     这个问题我们不能通过一个具体的算法得到答案,只有等到了明天才能验证得到正确答案,这就是NP类问题

    P/NP问题就是研究能否把NP类问题转变为P类问题。如果能,则P = NP 成立;否则,P != NP。

    回到目录…

    P = NP 成立吗?

    请添加图片描述

     我们先假设P = NP成立,那么给这个世界带来些什么影响呢?

     如果P=NP真的成立,那么对于任何一件随机的事件,我们都可以找出针对性的算法来计算或控制事件的走向。还是刚刚那个股市的例子,我们就可以计算出每支股票在未来的涨跌情况,这样岂不成了“股票之神”?在医疗上,我们可以解决很多目前无法攻克的疾病如癌症;在科技上,我们可以通过特定的算法来解决我们无法实现的技术难题;总之无论在哪个领域都会取得很大的突破。毫不夸张地说,甚至有可能做到跨越时间、空间,知晓未来、洞察于千里之外。
     当然,也存在一定的弊端,如对密码学的影响,破译密码会变得很容易。甚至会对计算机网络安全构成巨大的威胁。

     这虽然听起来好像很扯淡!但确实有很大一部分数学家和科学家在一直研究这个问题。那到底 P = NP 能否成立?有没有人证明了它的成立?或是证明了它不可能成立?

    学术界的最新消息:

    公元2010年:
     8 月 6 日,HP LAB的 Vinay Deolalikar 教授宣布证明了P!=NP,并且公布了证明过程。
     8 月 8 日,Lipton 在博客上讨论了这篇论文,给出了略显乐观的评价:这是一个值得认真对待的证明。这篇文章引来大量严肃的学术性回复,大多来自业内人士,各方看法不一。
     8 月 9 日,Lipton 写了一篇新的博客文章,指出了 Deolalikar 证明思路中的一些重大漏洞。
     8 月 10 日,Lipton 写了新的博客文章,试图将各方讨论的结果以更清晰的方式呈现出来。同日,Deolalikar 在自己的网站上撤下了论文初稿的链接,稍后放上了新一稿。
     8 月 11 日,Lipton 贴出了 Deolalikar 对一部分学术质疑的答复。Vinay Deolalikar 贴出了论文的第三稿。
     8 月 12 日,Lipton 贴出了一封来自 Neil Immerman 的信,指出了两个此前未被认真讨论的漏洞。
     8 月 13 日,Deolalikar 贴出了一篇关于自己的证明的解释性文档。
     8 月 14 日,在很多科学家的共同讨论中,人们逐渐理清 Deolalikar 的论文的根本问题在于把两个没有在论文中被严格定义出来的直观概念混淆在一起,从而做出了不完善的论证
     8 月 15 日,Lipton 贴出了他对于一周以来讨论的总结:Deolalikar的证明不能成立。随后的发言越来越多地集中于更抽象的层面,并且仍在继续。

    回到目录…

    总结

     截至到目前为止,P = NP? 问题的讨论还没有停止。没有人能拿出有力的证据证明等式成立。虽然有科学家拿出自己的论据来证明了P != NP,但是随后也发现了论据的漏洞,依然不能证明等式不成立。现在 P = NP? 依然是个谜!
     也许在很多人看来这个问题的讨论没有任何意义,觉得可能会走在一条错误的道路上。但就是有那么一部分数学家像“老林”一样,穷尽几十年来研究这个问题。可能这就是数学的魅力吧!

     OK! OK! 文章到此结束了。今天写这篇文章并不是想要真正探讨这个学术问题,一是为了缓解一下学习压力(毕竟最近一直学习Java),二是为了满足一下自己和大家的求知欲 (好奇心)。最后再次推荐一下这部剧——“天才基本法”,真的好看!

    回到目录…


    提示:这里对文章进行总结: 以上就是今天的学习内容,这篇文章不是Java课程的学习,而是谈谈一个学术问题。之后的学习内容将持续更新!!!
    展开全文
  • 1 基本概念 1.1 多项式和时间复杂度 (1)多项式 axn+bxn−1+cax^n+bx^{n-1}+caxn+bxn−1+c,形如这种形式的就被称为x的最高位为n的多项式。...1.2 P和NP (1)P(deterministic polynomial time quest
  • P问题、NP问题、NPC问题、NP-hard问题详解

    万次阅读 多人点赞 2018-09-19 18:44:24
    要理解P问题、NP问题、NPC问题、NP-hard问题,需要先弄懂几个概念: 什么是多项式时间? 什么是确定性算法?什么是非确定性算法? 什么是规约/约化? 多项式时间(Polynomial time) 什么是时间复杂度? 时间...
  • 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问题都能够被解决...
  • NP难问题求解综述

    万次阅读 2020-09-29 05:34:14
    摘要:定义NP问题及P类问题,并介绍一些常见的NP问题,以及NP问题的一些求解方法,最后最NP问题求解的发展方向做一些展望。 关键词:NP难问题 P类问题 算法 最优化问题 正文: 一.NP难问题及P类问题 为了解释NP...
  • 什么是 P = NP 问题?

    万次阅读 多人点赞 2020-04-19 12:15:00
    点击关注上方“五分钟学算法”,设为“置顶或星标”,第一时间送达干货。转自后端技术指南针1 前言今天和大家一起了解个高能知识点:P=NP问题。看到这里我们可能是一头雾水,不由得发问:P问题...
  • np.array()函数

    万次阅读 多人点赞 2021-12-28 15:16:32
    函数调用方法: numpy.array(object, dtype=None) ...array = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) print("数组array的值为: ") print(array) print("数组array的默认类型为: ") print(arr
  • 什么是P=NP问题?

    千次阅读 多人点赞 2020-04-02 11:46:34
    来自:后端技术指南针1 前言今天和大家一起了解个高能知识点:P=NP问题。看到这里我们可能是一头雾水,不由得发问:P问题是什么?NP问题又是什么?P=NP又是什么意思?研究并解决P=N...
  • 如何证明一个问题是NP-Hard或NP-Complete?

    万次阅读 多人点赞 2018-12-23 14:53:05
    文章目录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; ...
  • N、NP、NPC问题分析总结

    千次阅读 2022-01-25 16:26:41
    目录 一、时间复杂度 1、定义 2、多项式级别的复杂度 3、非多项式级别的复杂度 4、并非所有的问题都能够找到多项式级别时间复杂度的解法 二、P、NP、NPC问题 1、P问题 2、NP问题 3、一类特殊的NP问题 4、约化...
  • 【numpy】详解 np.nan和np.inf 的用法

    千次阅读 2021-11-28 20:11:20
    文章目录np.nan和np.infnp.nan什么时候numpy中会出现nan?np.nan 和np.nan 不相等统计t3中不等于0的个数统计t3中nan的个数有两种方式查看t3中是否有nan有两种方式把t3中nan的值替换为0nan和任何数值计算都为nannp....
  • NP问题总结(概念+例子+证明)

    万次阅读 多人点赞 2020-03-29 20:22:11
    本文是自己对NP问题的一次总结,因为看别的博客要不只讲概念,要不只有例子,算是一次汇总吧,加上自己的一点小理解,由于看了一段时间才进行总结的,有些图是直接用的别人画好的,但是不记得网址了,特此鸣谢~
  • P、NP、NPC和NP-Hard相关概念的图形和解释

    千次阅读 多人点赞 2019-01-12 22:34:48
    P、NP、NPC和NP-Hard相关概念的图形和解释 文章转自:https://blog.csdn.net/huang1024rui/article/details/49154507#commentBox 一、相关概念 &nbsp; &nbsp; &nbsp; P:&nbsp;能在多项式时间内...
  • np.concatenate()函数

    千次阅读 2020-10-15 14:33:22
    提到numpy的数组操作,我们就不得不说到np.concatenate()函数,concatenate在英文中是级联的意思,我们可以简单地理解为连接。代码如下: # -*- coding: utf-8 -*- import numpy as np class Debug: def __init__...
  • np.load和np.save是读写磁盘数组数据的两个主要函数,默认情况下,数组是以未压缩的原始二进制格式保存在扩展名为.npy的文件中。 他们会自动处理元素类型和形状等信息 np.save(file, arr, allow_pickle=True, fix_...
  • np.array与np.float32

    千次阅读 2021-07-17 15:31:43
    import numpy as np a = np.array([1, 2, 3, 4, 5], ndmin = 3) print (type(a),a) 打印结果:<class 'numpy.ndarray'> [[[1 2 3 4 5]]] import numpy as np a = np.array([1, 2, 3, 4, 5], ndmin = 2) ...
  • 记录一下numpy.array()的详细用法,以及与np.asarray()和np.ndarray()的区别。 目录 1. Numpy.array()详解 1.1 函数形式 1.2 参数详解 1.3 具体用法 2.Asarray和Array辨析 2.1 object对象是普通迭代序列时 ...
  • np.floor

    千次阅读 2021-11-13 17:29:01
    np.floor:向下取整 np.ceil:向上取整
  • np.around()函数用于返回四舍五入后的值,可指定精度。 np.floor()函数用于以元素方式返回输入的下限。 np.ceil()函数用于以元素方式返回输入的上限。 1、np.around np.around(a, decimals=0, out=None ) 对于...
  • 1、np.dot() 2、@ 3、np.multiply() 4、*
  • 【python】 np转base64, base64转np

    千次阅读 2022-04-18 20:53:35
    def numpy_to_base64(image_np): data = cv2.imencode('.jpg', image_np)[1] image_bytes = data.tobytes() image_base4 = base64.b64encode(image_bytes).decode('utf8') return image_base4 def base64_to_...
  • np.stack()函数详解

    万次阅读 多人点赞 2020-11-18 13:40:27
    np.stack()中axis参数的深入理解 看了一下大家关于np.stack()的理解,我感觉自己还是一知半解,有点蒙。自己又想把这个函数真正的理解 ,于是花了一点时间终于对这个函数有了自己的理解,决定把自己的想法写下来与...
  • 如何理解P和NP问题

    千次阅读 2020-05-28 22:20:30
    2000 年,美国克莱数学研究所公布了世界七大数学难题,又称千禧年大奖难题,规定对每一难题的破解者颁发一百万美元的奖金。其中 P 与 NP 问题被列为这七大数学难题之首,P与 NP 问题被列为七大世界数学难题之首。
  • np.newaxis()函数

    千次阅读 2022-04-13 14:49:54
    np.newaxis 的功能是增加新的维度,但是要注意 np.newaxis 放的位置不同,产生的矩阵形状也不同。 通常按照如下规则: np.newaxis 放在哪个位置,就会给哪个位置增加维度 x[:, np.newaxis] ,放在后面,会给列上增加...
  • np.delete详解

    千次阅读 2021-07-11 15:44:24
    np.delete(array,obj,axis) 二、函数的意思 array:需要处理的矩阵 obj:需要处理的位置,比如要删除的第一行或者第一行和第二行 axis: 如果输入为None:array会先按行展开,然后按照obj,删除第obj-1(从0开始)...
  • Python-Numpy函数:np.round(),np.around(),np.floor(),np.ceil()这几个函数均可以对numpy数组元素进行取整,区别以下。python 一 、np.round()函数的做用:对给定的数组进行四舍五入,能够指定精度,同np.around()...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 928,633
精华内容 371,453
关键字:

np

友情链接: delay_PWM.rar