什么是P = NP?问题

这篇具有很好参考价值的文章主要介绍了什么是P = NP?问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


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

引言

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

天才基本法

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

回到目录…文章来源地址https://www.toymoban.com/news/detail-457070.html

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

 这虽然听起来好像很扯淡!但确实有很大一部分数学家和科学家在一直研究这个问题。那到底 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课程的学习,而是谈谈一个学术问题。之后的学习内容将持续更新!!!

到了这里,关于什么是P = NP?问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Powershell删除文本指定内容所在行以下内容

    需求:批量获取文本指定内容所在行以下内容(含当前行)   解决方案:使用Powershell脚本处理   案例: 获取当前文件夹下所有txt文件 含文本\\\"4\\\"所在行 以下内容(含当前行) 如果有多行包含文本\\\"4\\\",取第一个所在行以下内容(含当前行)   1.查看当前文件夹内容   2.右键执

    2024年01月20日
    浏览(38)
  • 三个稠密矩阵A,B,C的乘积ABC,假设三个矩阵的尺寸分别为mn,np,pq,且m<n<p<q,以下计算顺序效率最高的是

    提示: 在深度学习中,涉及到大量矩阵相乘,现在需要计算三个稠密矩阵A,B,C的乘积ABC,假设三个矩阵的尺寸分别为m n,n p,p*q,且mnpq,以下计算顺序效率最高的是:() A(BC) (AB)C (AC)B 所有效率都相同 矩阵乘积数学公式: ​ 假设存在两个矩阵A为m×n矩阵,B为k×l矩阵,若需要计

    2024年02月13日
    浏览(46)
  • Element UI进行表单校验的时候,输入正确内容后,还有提示问题

    自己在进行表单验证时,明明输入了内容并且格式也正确,但是提示信息一直提示,在网上看了其它博主的文章解决了问题(字母写错啦真是脑残)在这里总结一下 出错原因:     1.看看你的el-form 是否绑定了值model并且model后面的名称是否和你后面表单输入时使用的名称相同

    2024年02月05日
    浏览(41)
  • 【error】svn 清理以下路径失败 原始内容不存在

    目前我们这边的内网代码是通过 TortoiseSVN 进行版本管理的,平时用着也挺好的,没碰到什么大问题。 但是,今天碰到了一个比较棘手的问题,在这里做一下记录,以方便自己和有需要的朋友在之后碰到该类问题时有个参考。 具体的错误现象如下图所示: 导致上述现象的步骤

    2024年02月15日
    浏览(36)
  • WPS解决插入公式在正文带来行间距变大问题

    写论文解释公式时,插入对应的变量,导致行间距变大,如图   显然上文与下文行间距不等。但无法通过修改数值修改下文行间距。

    2024年04月11日
    浏览(53)
  • NP-Hard?大白话学习P问题、NP问题、NP完全问题和NP难问题

    ## 该笔记自用为主,记录一些日常学习过程中看到的不熟悉的知识和从未接触过的知识,用于回看和记录。其中有一些个人理解,如有错误请讨论指正。 在讨论这一串问题之前,我们需要复习两个概念。 1.多项式和非多项式 多项式: 非多项式:或者 2.时间复杂度 在计算机算

    2024年02月09日
    浏览(56)
  • 【简述】【图】P类问题、NP类问题、NP完全问题和NP难问题

    1. P类问题(Polynomial Problem)          P类问题 是指 一类能够用确定性算法在多项式时间内求解的判定问题 。其实,在非正式的定义中,我们可以把那些在多项式时间内求解的问题当作P类问题。 2. NP类问题(Non-deterministic Polynomial Problem)         NP类问题不是非P类问

    2024年02月09日
    浏览(41)
  • 一文理解NP完全理论,NP问题,NPC问题

    在以往的算法中,所接触到的大都是多项式时间内可完成的算法,比如O(n),O(nlogn),O(n^2)…,但仍存在一些算法的时间复杂度为:O(n^logn),O(2^n),O(n!)是非多项式时间算法,当此类程序规模一旦过大,便成为目前的计算机解决不了的难题。因此尝试用NP完全理论进行理解。 目录 NP问

    2024年02月04日
    浏览(38)
  • 解决easyExcel按模板导出xlsx文件打开提示“发现xxx.xlsx中部分内容有问题,是否让我们尽量尝试恢复?”的问题

    最近项目一个需求要求将订单按照excel模板导出,其中商品有多行,需要动态插入行并且存在合并单元格的情况,使用easyExcel官网提供的demo的填充和合并单元格: 官网填充demo 官网合并单元格demo 按模板导出主要代码: 合并单元格的策略为: 当有多行商品导出的excel文件打开

    2024年02月13日
    浏览(55)
  • 解决在tinymce编辑器插入视频到正文后不能跳转播放的问题

    问题:在其他软件中上传了视频文件,而后将此视频文件插入到正文中,此视频文件 可以 点击进度条跳转进度;而在知了(出现bug的这个软件)中上传了视频文件,而后将此视频文件插入到正文中。此视频文件 无法 点击进度条跳转进度。 需求:希望可以在知了中上传视频

    2024年02月01日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包