芒果视频下载

詳細信息

P類(lei)問題(ti)(ti)：所有可以在(zai)多(duo)項式時(shi)間(jian)內(nei)求解的(de)判定(ding)問題(ti)(ti)構(gou)成P類(lei)問題(ti)(ti)。判定(ding)問題(ti)(ti)：判斷是否(fou)有一種能(neng)夠解決某一類(lei)問題(ti)(ti)的(de)能(neng)行算法(fa)的(de)研究課題(ti)(ti)。

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

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

舉例敘述

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

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