什么是p問題、np問題和npc問題(留存版)

　　

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