芒果视频下载

詳細信息

P類問(wen)題：所有可以在多(duo)項式時間(jian)內求解的(de)判(pan)定問(wen)題構成P類問(wen)題。判(pan)定問(wen)題：判(pan)斷(duan)是否(fou)有一種能夠解決某一類問(wen)題的(de)能行算法的(de)研究課題。

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

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

舉例敘述

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

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