什么是p問題、np問題和npc問題(存儲(chǔ)版)
【正文】 來解決，倘若B的時(shí)間復(fù)雜度比 A的時(shí)間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時(shí)間復(fù)雜度還是相同。這個(gè)道理非常簡單，就不必闡述了。好 了，從約化的定義中我們看到，一個(gè)問題約化為另一個(gè)問題，時(shí)間復(fù)雜度增加了，問題的應(yīng)用范圍也增大了。我們有理由相信，NPC問題是最復(fù)雜的問題。NPC問題的定義非常簡 單?？聪旅嬉焕?，不需要解釋你馬上就明白了。有輸出無論如何都不可能為True的邏輯電路嗎？有。└─→┤││└──┘上面這個(gè)邏輯電路中，無論輸入是什么，輸出都是False。攀登這個(gè)信息學(xué)的巔峰是我們這一代的 終極目標(biāo)。因此 說，正是因?yàn)镹PC問題的存在，P=NP變得難以置信。證明過程相當(dāng)復(fù)雜，其大概意思是說任意一個(gè)NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計(jì)算機(jī)內(nèi)部也不過是一些 0和1的運(yùn)算），因此對于一個(gè)NP問題來說，問題轉(zhuǎn)化為了求出滿足結(jié)果為True的一個(gè)輸入（即一個(gè)可行解）?；氐缴衔模o定一個(gè)邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。└→┤NOT ├→──┘┌──┐│└──┘││輸入1 ├→─┐這一類問題就是傳說中的NPC 問題，也就是NP完全問題。很顯然，約化具有一項(xiàng)重要的性質(zhì)：約化具有傳遞性。也就是說，問題A不比問題B難。按照這個(gè)規(guī)則把前一個(gè)問題轉(zhuǎn)換成后一 個(gè)問題，兩個(gè)問題就等價(jià)了。下文將花大量篇幅介紹NPC問題，你從中可以體會(huì)到NPC問 題使P=NP變得多么不可思議。這就是NP問 題。然后我就胡亂 畫了幾條線，說就這條吧。接下來引入NP問題的概念。P是英文單詞多項(xiàng)式的第一個(gè)字母。問題是這樣的：給你一個(gè)圖，問你能否找到一條經(jīng)過每個(gè)頂點(diǎn)一次且恰好一次（不遺漏也不重復(fù)）最后又走回來的路（滿足這個(gè)條件的 路徑叫做Hamilton回路）。也就是說，對于高速 處理數(shù)據(jù)的計(jì)算機(jī)來說，處理某一個(gè)特定數(shù)據(jù)的效率不能衡量一個(gè)程序的好壞，而應(yīng)該看當(dāng)這個(gè)數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運(yùn)行時(shí)間是否還是一樣，或者也跟 著慢了數(shù)百倍，或者變慢了數(shù)萬倍。下面的內(nèi)容都是在講什么是P問題，什么是NP問題，什么是NPC 問題，你如果不是很感興趣就可以不看了。你會(huì)經(jīng)?？吹骄W(wǎng)上出現(xiàn)“這怎么做，這不是NP問題嗎”、“這個(gè)只有搜了，這已 經(jīng)被證明是NP問題了”之類的話。不會(huì)存在O(2*n^2)的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)“2”是系數(shù)，根本不會(huì)影響到整個(gè)程序的時(shí)間增長。容易看出，前面的幾類復(fù)雜度被分為兩種級(jí)別，其中后者的復(fù)雜度無論如何都遠(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ī)往往不能承受。The Halting Problem就 是一個(gè)著名的不可解問題，在我的Blog上有過專門的介紹和證明。道理很簡單，一個(gè)用窮舉換來的非多項(xiàng)式級(jí)時(shí)間 的超時(shí)程序不會(huì)涵蓋任何有價(jià)值的算法。NP問題是指可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問題。別人會(huì)問他這 題怎么做出來的，他就可以說，因?yàn)槲艺业搅艘粋€(gè)比100 小的解。很顯然，
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1