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