芒果视频下载

詳細信息

P類問題(ti)(ti)(ti)(ti)：所有可以在多項式(shi)時間內求解的判定問題(ti)(ti)(ti)(ti)構(gou)成P類問題(ti)(ti)(ti)(ti)。判定問題(ti)(ti)(ti)(ti)：判斷是否有一(yi)種能夠解決某(mou)一(yi)類問題(ti)(ti)(ti)(ti)的能行算法的研究課題(ti)(ti)(ti)(ti)。

NP類(lei)問(wen)(wen)(wen)題(ti)(ti)：所有(you)(you)的(de)(de)非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)多(duo)項(xiang)(xiang)式(shi)時(shi)間(jian)(jian)可解(jie)的(de)(de)判(pan)定(ding)(ding)(ding)問(wen)(wen)(wen)題(ti)(ti)構(gou)成NP類(lei)問(wen)(wen)(wen)題(ti)(ti)。非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)算(suan)(suan)法(fa)：非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)算(suan)(suan)法(fa)將問(wen)(wen)(wen)題(ti)(ti)分解(jie)成猜(cai)(cai)測和驗(yan)(yan)證兩個(ge)階(jie)(jie)(jie)段。算(suan)(suan)法(fa)的(de)(de)猜(cai)(cai)測階(jie)(jie)(jie)段是(shi)(shi)(shi)非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)的(de)(de)，算(suan)(suan)法(fa)的(de)(de)驗(yan)(yan)證階(jie)(jie)(jie)段是(shi)(shi)(shi)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)的(de)(de)，它驗(yan)(yan)證猜(cai)(cai)測階(jie)(jie)(jie)段給(gei)出(chu)解(jie)的(de)(de)正(zheng)確(que)性(xing)(xing)(xing)。設算(suan)(suan)法(fa)A是(shi)(shi)(shi)解(jie)一個(ge)判(pan)定(ding)(ding)(ding)問(wen)(wen)(wen)題(ti)(ti)Q的(de)(de)非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)算(suan)(suan)法(fa)，如(ru)果(guo)(guo)A的(de)(de)驗(yan)(yan)證階(jie)(jie)(jie)段能(neng)在多(duo)項(xiang)(xiang)式(shi)時(shi)間(jian)(jian)內完成，則稱(cheng)A是(shi)(shi)(shi)一個(ge)多(duo)項(xiang)(xiang)式(shi)時(shi)間(jian)(jian)非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)算(suan)(suan)法(fa)。有(you)(you)些計(ji)(ji)算(suan)(suan)問(wen)(wen)(wen)題(ti)(ti)是(shi)(shi)(shi)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)的(de)(de)，例如(ru)加減乘除，只(zhi)(zhi)要(yao)按照公式(shi)推(tui)導(dao)，按部(bu)就(jiu)班一步(bu)(bu)步(bu)(bu)來(lai)(lai)，就(jiu)可以得到結(jie)果(guo)(guo)。但(dan)是(shi)(shi)(shi)，有(you)(you)些問(wen)(wen)(wen)題(ti)(ti)是(shi)(shi)(shi)無法(fa)按部(bu)就(jiu)班直接(jie)(jie)地計(ji)(ji)算(suan)(suan)出(chu)來(lai)(lai)。比如(ru)，找大(da)質數的(de)(de)問(wen)(wen)(wen)題(ti)(ti)。有(you)(you)沒有(you)(you)一個(ge)公式(shi)能(neng)推(tui)出(chu)下一個(ge)質數是(shi)(shi)(shi)多(duo)少呢(ni)？這(zhe)(zhe)種問(wen)(wen)(wen)題(ti)(ti)的(de)(de)答(da)案，是(shi)(shi)(shi)無法(fa)直接(jie)(jie)計(ji)(ji)算(suan)(suan)得到的(de)(de)，只(zhi)(zhi)能(neng)通過間(jian)(jian)接(jie)(jie)的(de)(de)“猜(cai)(cai)算(suan)(suan)”來(lai)(lai)得到結(jie)果(guo)(guo)。這(zhe)(zhe)也就(jiu)是(shi)(shi)(shi)非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)問(wen)(wen)(wen)題(ti)(ti)。而(er)這(zhe)(zhe)些問(wen)(wen)(wen)題(ti)(ti)的(de)(de)通常(chang)有(you)(you)個(ge)算(suan)(suan)法(fa)，它不能(neng)直接(jie)(jie)告訴(su)(su)(su)你(ni)答(da)案是(shi)(shi)(shi)什么(me)，但(dan)可以告訴(su)(su)(su)你(ni)，某個(ge)可能(neng)的(de)(de)結(jie)果(guo)(guo)是(shi)(shi)(shi)正(zheng)確(que)的(de)(de)答(da)案還(huan)是(shi)(shi)(shi)錯誤的(de)(de)。這(zhe)(zhe)個(ge)可以告訴(su)(su)(su)你(ni)“猜(cai)(cai)算(suan)(suan)”的(de)(de)答(da)案正(zheng)確(que)與(yu)否的(de)(de)算(suan)(suan)法(fa)，假如(ru)可以在多(duo)項(xiang)(xiang)式(shi)（polynomial）時(shi)間(jian)(jian)內算(suan)(suan)出(chu)來(lai)(lai)，就(jiu)叫做(zuo)多(duo)項(xiang)(xiang)式(shi)非(fei)確(que)定(ding)(ding)(ding)性(xing)(xing)(xing)問(wen)(wen)(wen)題(ti)(ti)。

NPC問(wen)題(ti)(ti)(ti)：NP中的(de)某些(xie)(xie)問(wen)題(ti)(ti)(ti)的(de)復雜性與整個(ge)類的(de)復雜性相關聯.這些(xie)(xie)問(wen)題(ti)(ti)(ti)中任何一個(ge)如(ru)果存在多(duo)項式時間(jian)的(de)算法,那么所有NP問(wen)題(ti)(ti)(ti)都是多(duo)項式時間(jian)可(ke)解的(de).這些(xie)(xie)問(wen)題(ti)(ti)(ti)被稱為NP-完(wan)全問(wen)題(ti)(ti)(ti)(NPC問(wen)題(ti)(ti)(ti))。

舉例敘述

在一個(ge)(ge)周六的晚上，你(ni)參加了一個(ge)(ge)盛大(da)的晚會(hui)。由于感(gan)到局促不安(an)，你(ni)想知道這(zhe)一大(da)廳(ting)(ting)中是否有你(ni)已經認識的人。你(ni)的主(zhu)人向你(ni)提議說，你(ni)一定認識那位正(zheng)在甜點盤附近角(jiao)落(luo)的女士羅絲。不費(fei)一秒鐘，你(ni)就能向那里掃視(shi)，并且發現你(ni)的主(zhu)人是正(zheng)確(que)的。然而，如(ru)果沒有這(zhe)樣的暗示，你(ni)就必(bi)須環顧整個(ge)(ge)大(da)廳(ting)(ting)，一個(ge)(ge)個(ge)(ge)地審視(shi)每(mei)一個(ge)(ge)人，看是否有你(ni)認識的人。

生成問(wen)題(ti)的(de)(de)(de)一(yi)(yi)(yi)(yi)(yi)個(ge)(ge)(ge)解(jie)通(tong)常比(bi)驗(yan)(yan)證一(yi)(yi)(yi)(yi)(yi)個(ge)(ge)(ge)給(gei)定(ding)的(de)(de)(de)解(jie)時(shi)間(jian)花(hua)費要多(duo)(duo)得(de)多(duo)(duo)。這是(shi)(shi)(shi)(shi)這種一(yi)(yi)(yi)(yi)(yi)般現象的(de)(de)(de)一(yi)(yi)(yi)(yi)(yi)個(ge)(ge)(ge)例子。與此類(lei)似的(de)(de)(de)是(shi)(shi)(shi)(shi)，如果某(mou)人告訴你(ni)(ni)，數13,717,421可(ke)以(yi)(yi)(yi)寫(xie)成兩個(ge)(ge)(ge)較小的(de)(de)(de)數的(de)(de)(de)乘積(ji)，你(ni)(ni)可(ke)能(neng)(neng)不(bu)知道是(shi)(shi)(shi)(shi)否(fou)應該(gai)相信他，但是(shi)(shi)(shi)(shi)如果他告訴你(ni)(ni)他可(ke)以(yi)(yi)(yi)因(yin)式(shi)(shi)分解(jie)為(wei)(wei)3607乘上3803，那么你(ni)(ni)就可(ke)以(yi)(yi)(yi)用一(yi)(yi)(yi)(yi)(yi)個(ge)(ge)(ge)袖珍(zhen)計算(suan)器容易驗(yan)(yan)證這是(shi)(shi)(shi)(shi)對(dui)的(de)(de)(de)。人們發現，所(suo)有(you)的(de)(de)(de)完全多(duo)(duo)項式(shi)(shi)非確(que)定(ding)性(xing)問(wen)題(ti)，都可(ke)以(yi)(yi)(yi)轉換為(wei)(wei)一(yi)(yi)(yi)(yi)(yi)類(lei)叫做(zuo)滿(man)足性(xing)問(wen)題(ti)的(de)(de)(de)邏(luo)輯運算(suan)問(wen)題(ti)。既然這類(lei)問(wen)題(ti)的(de)(de)(de)所(suo)有(you)可(ke)能(neng)(neng)答案，都可(ke)以(yi)(yi)(yi)在(zai)多(duo)(duo)項式(shi)(shi)時(shi)間(jian)內(nei)計算(suan)，人們于(yu)是(shi)(shi)(shi)(shi)就猜想(xiang)，是(shi)(shi)(shi)(shi)否(fou)這類(lei)問(wen)題(ti)，存在(zai)一(yi)(yi)(yi)(yi)(yi)個(ge)(ge)(ge)確(que)定(ding)性(xing)算(suan)法，可(ke)以(yi)(yi)(yi)在(zai)多(duo)(duo)項式(shi)(shi)時(shi)間(jian)內(nei)，直接算(suan)出或是(shi)(shi)(shi)(shi)搜(sou)尋出正(zheng)確(que)的(de)(de)(de)答案呢？這就是(shi)(shi)(shi)(shi)著名的(de)(de)(de)NP=P？的(de)(de)(de)猜想(xiang)。 不(bu)管我們編寫(xie)程序是(shi)(shi)(shi)(shi)否(fou)靈(ling)巧，判定(ding)一(yi)(yi)(yi)(yi)(yi)個(ge)(ge)(ge)答案是(shi)(shi)(shi)(shi)可(ke)以(yi)(yi)(yi)很快利用內(nei)部知識來驗(yan)(yan)證，還是(shi)(shi)(shi)(shi)沒(mei)有(you)這樣的(de)(de)(de)提示而需(xu)要花(hua)費大(da)量時(shi)間(jian)來求解(jie)，被看(kan)作(zuo)邏(luo)輯和計算(suan)機科學中突出的(de)(de)(de)問(wen)題(ti)之一(yi)(yi)(yi)(yi)(yi)。它是(shi)(shi)(shi)(shi)斯蒂文·考克于(yu)1971年陳述的(de)(de)(de)。