【正文】 解決一個(gè)問(wèn)題時(shí)，我們選擇的算法通常都需要是多項(xiàng)式級(jí)的復(fù)雜度，非多項(xiàng)式級(jí)的復(fù)雜度需要的 時(shí)間太多，往往會(huì)超時(shí)，除非是數(shù)據(jù)規(guī)模非常小。好，行了，基本上這個(gè)誤解已經(jīng)被澄清了。那么，根據(jù)這個(gè)定義，我也能舉出一個(gè)不大可能會(huì)有多項(xiàng)式級(jí)算法的問(wèn)題 來(lái)：Hamilton回路。我猜到的方案總是最優(yōu)的，不滿足題意的方案也不會(huì)來(lái)騙我去選它。“問(wèn)題A可約化為問(wèn)題B”有一個(gè)重要的 直觀意義：B的時(shí)間復(fù)雜度高于或者等于A的時(shí)間復(fù)雜度?，F(xiàn)在再來(lái)說(shuō)一下約化的標(biāo)準(zhǔn)概念就不難理解了：如果能找到這樣一個(gè)變化法則，對(duì)任意一個(gè)程序A的輸入，都能按這個(gè)法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說(shuō)，問(wèn)題A可約化為問(wèn)題B。這種問(wèn)題的存在難以置信，并且更加不可思議的是，這種問(wèn)題不只一個(gè)，它有很多個(gè)，它是一類問(wèn)題。事實(shí)上，由于NPHard放寬了限定條件，它將有可能比所有的NPC問(wèn)題的時(shí)間復(fù)雜度更 高從而更難以解決。因此，邏輯電路問(wèn)題是NPC類問(wèn)題的“鼻祖”。│ 輸入1├─→┐└─→┤┌───┐│現(xiàn)在被證明是NPC問(wèn)題的有很多，任何一個(gè)找到了多項(xiàng)式算法的話所有的NP問(wèn)題都可以完美解決了。我們就說(shuō)，這個(gè)邏輯電路不存在使輸出為True的一組輸入。└──┘順便講一下NPHard問(wèn)題。同時(shí)滿足下面兩個(gè)條件的問(wèn)題就是NPC問(wèn)題。通過(guò)對(duì)某些問(wèn)題的不斷約化，我們能夠不斷尋找復(fù)雜度 更高，但應(yīng)用范圍更廣的算法來(lái)代替復(fù)雜度雖然低，但只能用于很小的一類問(wèn)題的算法。NP問(wèn)題一直都是信息學(xué)的巔峰。我們不會(huì)指望一個(gè)連多項(xiàng)式地驗(yàn)證一個(gè) 解都不行的問(wèn)題存在一個(gè)解決它的多項(xiàng)式級(jí)的算法。別人會(huì)問(wèn)他這 題怎么做出來(lái)的，他就可以說(shuō)，因?yàn)槲艺业搅艘粋€(gè)比100 小的解。道理很簡(jiǎn)單，一個(gè)用窮舉換來(lái)的非多項(xiàng)式級(jí)時(shí)間 的超時(shí)程序不會(huì)涵蓋任何有價(jià)值的算法。The Halting Problem就 是一個(gè)著名的不可解問(wèn)題，在我的Blog上有過(guò)專門的介紹和證明。不會(huì)存在O(2*n^2)的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)“2”是系數(shù)，根本不會(huì)影響到整個(gè)程序的時(shí)間增長(zhǎng)。你會(huì)經(jīng)?？吹骄W(wǎng)上出現(xiàn)“這怎么做，這不是NP問(wèn)題嗎”、“這個(gè)只有搜了，這已 經(jīng)被證明是NP問(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)倍。P是英文單詞多項(xiàng)式的第一個(gè)字母。然后我就胡亂 畫了幾條線，說(shuō)就這條吧。下文將花大量篇幅介紹NPC問(wèn)題，你從中可以體會(huì)到NPC問(wèn) 題使P=NP變得多么不可思議。按照這個(gè)規(guī)則把前一個(gè)問(wèn)題轉(zhuǎn)換成后一 個(gè)問(wèn)題，兩個(gè)問(wèn)題就等價(jià)了。很顯然，約化具有一項(xiàng)重要的性質(zhì)：約化具有傳遞性。│輸入1 ├→─┐└──┘│證明過(guò)程相當(dāng)復(fù)雜，其大概意思是說(shuō)任意一個(gè)NP問(wèn)題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計(jì)算機(jī)內(nèi)部也不過(guò)是一些 0和1的運(yùn)算），因此對(duì)于一個(gè)NP問(wèn)題來(lái)說(shuō)，問(wèn)題轉(zhuǎn)化為了求出滿足結(jié)果為True的一個(gè)輸入（即一個(gè)可行解）。攀登這個(gè)信息學(xué)的巔峰是我們這一代的 終極目標(biāo)。└──┘│└─→┤有輸出無(wú)論如何都不可能為True的