什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題-wenkub
2022-09-02 18:58:53 本頁(yè)面
【正文】 Problem就 是一個(gè)著名的不可解問(wèn)題，在我的Blog上有過(guò)專(zhuān)門(mén)的介紹和證明。容易看出，前面的幾類(lèi)復(fù)雜度被分為兩種級(jí)別，其中后者的復(fù)雜度無(wú)論如何都遠(yuǎn)遠(yuǎn)大于前者：一種是 O(1),O(log(n)),O(n^a)等，我們把它叫做多項(xiàng)式級(jí)的復(fù)雜度，因?yàn)樗囊?guī)模n出現(xiàn)在底數(shù)的位置；另一種是O(a^n)和O(n!)型復(fù) 雜度，它是非多項(xiàng)式級(jí)的，其復(fù)雜度計(jì)算機(jī)往往不能承受。不會(huì)存在O(2*n^2)的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)“2”是系數(shù)，根本不會(huì)影響到整個(gè)程序的時(shí)間增長(zhǎng)。時(shí)間復(fù)雜度并不是表示一個(gè)程序解決問(wèn)題需要花多少時(shí)間，而是當(dāng)問(wèn)題規(guī)模擴(kuò)大后，程序需要的時(shí)間長(zhǎng)度增長(zhǎng)得有多快。好，行了，基本上這個(gè)誤解已經(jīng)被澄清了。你會(huì)經(jīng)常看到網(wǎng)上出現(xiàn)“這怎么做，這不是NP問(wèn)題嗎”、“這個(gè)只有搜了，這已 經(jīng)被證明是NP問(wèn)題了”之類(lèi)的話。你要知道，大多數(shù)人此時(shí)所說(shuō)的NP問(wèn)題其實(shí)都是指的NPC問(wèn)題。下面的內(nèi)容都是在講什么是P問(wèn)題，什么是NP問(wèn)題，什么是NPC 問(wèn)題，你如果不是很感興趣就可以不看了。也就是說(shuō)，對(duì)于高速 處理數(shù)據(jù)的計(jì)算機(jī)來(lái)說(shuō)，處理某一個(gè)特定數(shù)據(jù)的效率不能衡量一個(gè)程序的好壞，而應(yīng)該看當(dāng)這個(gè)數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運(yùn)行時(shí)間是否還是一樣，或者也跟 著慢了數(shù)百倍，或者變慢了數(shù)萬(wàn)倍。同樣地，O (n^3+n^2)的復(fù)雜度也就是O(n^3)的復(fù)雜度。當(dāng)我們?cè)诮鉀Q一個(gè)問(wèn)題時(shí)，我們選擇的算法通常都需要是多項(xiàng)式級(jí)的復(fù)雜度，非多項(xiàng)式級(jí)的復(fù)雜度需要的 時(shí)間太多，往往會(huì)超時(shí)，除非是數(shù)據(jù)規(guī)模非常小。再比如，輸出從1到n這n個(gè)數(shù)的全排列。問(wèn)題是這樣的：給你一個(gè)圖，問(wèn)你能否找到一條經(jīng)過(guò)每個(gè)頂點(diǎn)一次且恰好一次（不遺漏也不重復(fù)）最后又走回來(lái)的路（滿足這個(gè)條件的 路徑叫做Hamilton回路）。P是英文單詞多項(xiàng)式的第一個(gè)字母。接下來(lái)引入NP問(wèn)題的概念。NP問(wèn)題的另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的 問(wèn)題。然后我就胡亂 畫(huà)了幾條線，說(shuō)就這條吧。在這個(gè)題中，找一個(gè)解很困難，但驗(yàn)證一個(gè)解很容易。這就是NP問(wèn) 題。但我要把 問(wèn)題換成這樣：試問(wèn)一個(gè)圖中是否不存在Hamilton回路。相信讀者很快明白，信息學(xué)中的號(hào)稱最困難的問(wèn)題——“NP問(wèn)題”，實(shí)際上是在探討NP問(wèn)題與P類(lèi)問(wèn)題的關(guān) 系。我們可以再用集合的觀點(diǎn)來(lái)說(shuō)明。巔峰，意即很引人注目但難以解決。人們普遍認(rèn)為，P=NP不成立，也就是說(shuō)，多數(shù)人相信，存在至少一個(gè)不可能有多項(xiàng)式 級(jí)復(fù)雜度的算法的NP問(wèn)題。下文將花大量篇幅介紹NPC問(wèn)題，你從中可以體會(huì)到NPC問(wèn) 題使P=NP變得多么不可思議。比 如說(shuō)，現(xiàn)在有兩個(gè)問(wèn)題：求解一個(gè)一元一次方程和求解一個(gè)一元二次方程。按照這個(gè)規(guī)則把前一個(gè)問(wèn)題轉(zhuǎn)換成后一 個(gè)問(wèn)題，兩個(gè)問(wèn)題就等價(jià)了。也就是說(shuō)，問(wèn)題A不比問(wèn)題B難。很顯然，約化具有一項(xiàng)重要的性質(zhì)：約化具有傳遞性。當(dāng)然，我們所說(shuō)的“可約化”是指的可“多項(xiàng)式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項(xiàng)式的時(shí)間里完成的。再回想前面講的P和NP問(wèn)題，聯(lián)想起約化的傳遞性，自然地，我們會(huì)想 問(wèn)，如果不斷地約化上去，不斷找到能“通吃”若干小NP問(wèn)題的一個(gè)稍復(fù)雜的大NP問(wèn)題
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1