np是什么(np问题是什么意思)

在计算机理论研究中,最广为人知的问题莫过于 P 和 NP 的相等与否问题。这个问题从计算复杂度被定义的那一刻开始,就伴随着所有理论计算机的研究工作。如今,这个问题已经成为计算机理论研究中最重要的问题,也被归类为百万美元奖金问题中的头号难题。至今为止,计算机理论科学家们都并没有能够证明 P 和 NP 之间的关系。

P =? NP

要想了解 P = NP 问题,首先我们要知道什么是 P,什么是 NP。我们知道,每一个问题都分为可解(decidable)和不可解(undecidable)的,所谓可解,就是这个问题至少有一个算法能够让一台计算机运行后得出正确结果,而所谓不可解,就是永远不可能存在一个算法来在任何一台计算机上计算它并且得出正确结论。而针对所有可解的问题,它可能拥有不止一个算法,而这些算法中,就会有复杂度之分。简而言之,有些算法运行的快,有些算法运行的慢,而这就是所谓的算法复杂度。

P 和 NP

如果有一个问题,存在一个算法能够在多项式时间内结束运行并且得出正确结论,那么我们将这个问题归类为 P 问题,同时,我们也认为这类问题是容易的。反之,如果有一个问题,存在一个对应的算法能够在指数时间内解出这个问题并得出正确结论,那么我们将其成为 NP 问题。很明显,所有 P 问题都属于 NP 问题,因为多项式时间永远短于指数时间,但是,是否所有的 NP 问题都属于 P 问题,这就是著名的 P = NP 问题。

证明手段

为了证明 P 和 NP 的相等性或不等性,我们引入另一个问题归类,也就是 NP 完全问题。如果有一个问题,我们针对其写出一个算法,而这个算法可以用来计算所有 NP 问题,那么这个问题就被称为 NP 完全问题,同时我们也称这个问题是困难的。简而言之,只要我们能够解决一个 NP 完全问题,那么我们可以解决所有 NP 问题。因此,假如我们能够证明任何一个 NP 完全问题其实也是一个 P 问题,那么我们就证得了 P = NP,反之,假如我们能够证明任何一个 NP 完全问题不可能拥有一个多项式时间内运行的算法,那么我们就证明了 P 和 NP 的不等性。

P = NP 的逻辑性冲突

在多年的研究中,绝大多数理论学家们相信,P 和 NP 是不想等的,因为如果它们相等,会造成一连串不可预测的结果。

我们知道,P 问题又被称为简单问题,NP 完全问题又被成为困难问题,假如 P = NP,也就是说所有的困难问题都能被简单的解决,甚至是说,世界上所有的问题都能够被简单的解决。我们在逻辑层面上相信,抄写一本数学书和撰写一本数学书是不同的,而撰写一本数学书哦要比抄写一本数学书难得多。然而,假如 P 和 NP 相等,撰写一本数学书和抄写一本数学书是同样难的。然而,除了我们的逻辑,我们没有任何证据能够证明 P 和 NP 的不相等性。

同时,相当多的计算机应用也是建立在 P 和 NP 的不相等上的。最值得提到的就是密码学的应用。可以说,现今所有的密码,在一定层面上都是“可破解的”。假设破解一个密码需要一个算法运行最少七天,而我们能做的就是在七天之内修改密码。然而,如果 P = NP,那么所有破解过程都是“容易的”,因而,整个密码学的根基都会动摇。

最后,我们相信,如果 P =?NP 问题得证,其证明应当是相当简洁明了的,如同图灵的 Halting Problem 证明一般巧妙。

(0)

相关推荐

  • Fine什么意思中文(fine的中文谐音是什么意思)

    欢迎来到“民不聊生”,“民不聊生”不聊不熟悉的事,您好,我是郭卫民,我们继续聊英语,聊《全方位英语单词记忆》。 《全方位英语单词记忆》系统是将英语单词进行较完全的拆分,针对拆分后得到的字母结合英语单词本身的含义引入象形、谐音、联想、图像和发音近似音并组合成助记句式对英语单词进行全方位的有效记忆。 今天带来的五个英语单词是: fine [fain] (身体)很…

    2022年8月6日
    600
  • 受益匪浅什么意思(如诉如泣什么意思)

    人教版小学语文四年级上册四字词语及解释

    2022年8月6日
    500
  • hd什么意思(饭圈用语hd是什么意思)

    现在越来许多的人开始留意到自己手机的最上端,状态栏上多出了一个\”HD\”,有的手机是volte的字母标识,以前没有的。那么这是什么意思呢?当我们手机上段状态栏出现字母hd或者volte标识,就代表说明我们的手机已经开通了高清通话功能,开通这个功能后,首先我们要知道的是:当你的手机状态栏出现HD或者volte字母标识,就表示你处在VO…

    2022年7月8日
    10.0K00
  • 佚名什么意思怎么读(焉怎么读)

    作者 陈婷刘丹 张康娅 李云胜 “我们是光明的使者,因为我们用火把文明与野蛮分开;我们创造了新的生活,因为我们把人生滋味调和得丰富多彩。”在餐饮人眼里,孙跃廷是位诗人,在诗人里他是餐饮专家。他的诗歌为厨师、为餐饮、为文化,于是这首脍炙人口的《我是一名厨师》应运而生。 一、传说中的“佚名” 厨师界流传着一首诗,这首诗题目就叫《我是一名厨师》。每逢厨师学校的新生…

    2022年6月27日
    10.1K00
  • 麻将多少张(清一色暗示什么意思)

    一、牌数 扬中麻将一共144张麻将牌,1-9筒、1-9条、1-9万、东南西北中发白各4张,春夏秋冬梅兰菊竹各1张。 二、庄家 (1)第一局由房主坐庄。 (2)之后谁胡牌谁坐庄。 (3)流局不换庄。 三、玩法特点 (1)操作:能吃、碰、杠。 (2)胡牌:可点炮,可自摸,可抢杠胡。 (3)补花: a.摸到花牌时,系统自动将花牌单独摆出,并从牌墙补牌,有几张花牌补…

    2022年6月27日
    10.0K00
  • introduce什么意思(instruction是什么意思)

    内容目录: 1. 核心词汇总结及详解; 2. 复杂句式分析; 3. 各题答案详解。 My stutter(口吃)had always been much of a problem. I’d had so many specialists for my______35________ over the years. As l walked down the h…

    2022年8月6日
    500
  • 往届生改应届生什么意思(校招非应届生)

    当年不会被其他高校录取 根据教育部规定,考生被正式录取后,高校和考生都不得以任何理由退档。考生今年也不得再填报任何志愿、不得再被其他学校录取。大学开学后,若考生逾期未报到,相当于自动放弃,学校将对考生作自动退学处理。 可能会出现重复学籍 一般来说高校学籍都是在开学时进行注册的,但总会有人为疏忽,即使本人没有前去报到,仍然被注册了学籍。如果复读后考上了另一所大…

    好闻分享 2022年8月5日
    600
  • 今日南宁土鸡肉鸡价(土鸡什么意思)

    市场上的在十元左右,目前来看,上涨0点05元/斤。销量环比小幅减少。 终端市场消费需求恢复缓慢,今天的鸡肉,今年1月16日至今年3月1日,特别好吃的,一直受青睐,远超去年同期同比增长40左右,没有后续下降的可能,白羽肉毛鸡市场今日白羽肉毛鸡价格继续上涨目前适重白羽肉毛鸡数量有限。并积极促,鸡心鸡肝13以上为肉鸡价格行情价格。 操作上建议稳步上调价格,明天的鸡…

    好闻分享 2022年8月7日
    500
  • 搭讪是什么意思(主动搭讪什么意思)

    当我们希望内心那些我们所欣赏的人时 ,金牛大厦,我们才能开启与之交往的序幕。事实上,搭讪的意思是仅是简单意义上的与陌生人交流,致我们所应该具备的一种社交破冰能力。 第一:克服恐惧心理 第二:洞悉防备心理。 事实上,这种应激性但缝背心在我们排位对单身者作出有效判断时会愈发强烈,因为人往往对未知的事物有着本能的排斥。 首先你要在外形上给对方良好的第一印象,臂如,…

    好闻分享 2022年8月6日
    500
  • 趋之若鹜什么意思(趋之若鹜近义词)

    易误用褒贬的成语 【暗送秋波】原指暗中眉目传情。后泛指献媚取宠,暗中勾结。 【半斤八两】比喻彼此一样,不相上下(多含贬义)。 【别出机杼】独创一格,与众不同。 【不以为然】不认为是对的,表示不同意(多含轻视意)。 【惨淡经营】指苦心费力经营。 【彻头彻尾】从头到尾,完完全全(多用于贬义)。 【惩前毖后】吸取过去失败的教训,以后小心,不致重犯错误。毖,谨慎,小…

    好闻分享 2022年8月6日
    800

发表评论

您的电子邮箱地址不会被公开。




分享本页
返回顶部