芒果视频下载

詳細信息

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

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

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

舉例敘述

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

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