芒果视频下载

詳細信息

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

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

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

舉例敘述

在一(yi)個(ge)(ge)周六的(de)晚(wan)上(shang)，你(ni)參加了一(yi)個(ge)(ge)盛大的(de)晚(wan)會(hui)。由于感到局(ju)促不安，你(ni)想知道(dao)這一(yi)大廳中(zhong)是(shi)否有你(ni)已經(jing)認(ren)(ren)識的(de)人(ren)(ren)。你(ni)的(de)主(zhu)人(ren)(ren)向(xiang)你(ni)提議說，你(ni)一(yi)定認(ren)(ren)識那位(wei)正在甜(tian)點盤(pan)附近角落的(de)女士羅絲。不費一(yi)秒(miao)鐘，你(ni)就(jiu)能向(xiang)那里掃視(shi)，并且發(fa)現你(ni)的(de)主(zhu)人(ren)(ren)是(shi)正確的(de)。然(ran)而，如果沒(mei)有這樣(yang)的(de)暗示，你(ni)就(jiu)必須環(huan)顧整(zheng)個(ge)(ge)大廳，一(yi)個(ge)(ge)個(ge)(ge)地審視(shi)每一(yi)個(ge)(ge)人(ren)(ren)，看是(shi)否有你(ni)認(ren)(ren)識的(de)人(ren)(ren)。

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