什么是p問題、np問題和npc問題(更新版)
【正文】 序總能得到一樣的結(jié)果。C是英文單詞“完全”的第一個字母?，F(xiàn)在，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？通常所謂的“NP問 題”，其實就一句話：證明或推翻P=NP。那么，只要我RP好，猜得準，我一定能在多項式的時間里解決這個問題?，F(xiàn)在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小于100個單位長度 的路線。有人說，這樣的“問題”不是一個“正規(guī)”的問題，正規(guī)的問題是讓程序解決一個問題，輸出一個“YES”或“NO”（這 被稱為判定性問題），或者一個什么什么的最優(yōu)值（這被稱為最優(yōu)化問題）。我們也說，O(n^100)的復雜度小 于O(^n)的復雜度。還是先用幾句話簡單 說明一下時間復雜度。NP問題并 不是那種“只有搜才行”的問題，NPC問題才是。這或許是眾多OIer最大的誤區(qū)之一。他們沒有搞清楚NP問題和NPC問題的概念。因此，我們會說，一個O(*n^3)的程序的效率比O(100*n^2)的效率低，盡管 在n很小的時候，前者優(yōu)于后者，但后者時間隨數(shù)據(jù)規(guī)模增長得慢，最終O(n^3)的復雜度將遠遠超過O(n^2)。不管你用什么方法，你的復雜度都是階乘級，因為 你總得用階乘級的時間打印出結(jié)果來。比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準。驗證一個解只需要O(n)的時間復雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加 出來。這樣問題就沒法在多項式的時間里進行驗證了，因為除非你試過所有的路，否則你不敢斷定它“沒 有Hamilton回路”。如果把所有P類 問題歸為一個集合P中，把所有 NP問題劃進另一個集合NP中，那么，顯然有P屬于NP。在信息學研究中，這是一個耗費了很多時間和精力也沒有解決的終極問題，好比物理學中的大統(tǒng)一和數(shù)學中的歌德巴赫猜想等。人們?nèi)绱藞孕臥≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP完全問題，也即所謂的 NPC問題。為了說明NPC問題，我們先引入一個概念——約化(Reducibility，有的資料上叫“歸約”)。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一 元一次方程。約化的過程只有用多項式的時間完成才有意義。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。到此為止，本文已經(jīng)寫了近5000字了，我佩服你還能看到這里來，同時也佩服一下自己能寫到這里來。證明一個問題是 NPC問題也很簡單。因此，前文才說，“正是NPC問題的存在，使人們相信P≠NP”。NPHard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。NPC問題是存在的。這是第一個NPC問題。┌───┐└───┘│┌───┐│┌──┐└───┘│└───┘這是個較簡單的邏輯電路，當輸入輸入輸入3分別為True、True、False或False、True、False時，輸出為True。邏 輯電路問題屬于NPC問題。有了第一個NPC 問題后，一大堆NPC問題就出現(xiàn)了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它
公司管理相關(guān)推薦
鄂ICP備17016276號-1