資源描述：
《轉(zhuǎn)載：澄清P問題、NP問題、NPC問題的概念》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、轉(zhuǎn)載：澄清P問題、NP問題、NPC問題的概念你會經(jīng)?？吹骄W(wǎng)上出現(xiàn)“這怎么做，這不是NP問題嗎”、“這個只有搜了，這已經(jīng)被證明是NP問題了”之類的話。你要知道，大多數(shù)人此時所說的NP問題其實(shí)都是指的NPC問題。他們沒有搞清楚NP問題和NPC問題的概念。NP問題并不是那種“只有搜才行”的問題，NPC問題才是。好，行了，基木上這個課解已經(jīng)被澄清了。下面的內(nèi)容都是在講什么是P問題，什么是NP問題，什么是NPC問題，你如果不是很感興趣就可以不看了。接下來你可以看到，把NP問題當(dāng)成是NPC問題是一個多大的錯誤。還是先用兒句話簡單說明一下時間復(fù)雜度。時間復(fù)雜度并不是表
2、示一個程序解決問題需要花多少時間，而是當(dāng)問題規(guī)模擴(kuò)人后，程序需要的時間長度增長得有多快。也就是說，對于高速處理數(shù)據(jù)的計算機(jī)來說，處理某一個特定數(shù)據(jù)的效率不能衡竝一個程序的好壞，而應(yīng)該看當(dāng)這個數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運(yùn)行時間是否還是一樣，或者也跟著慢了數(shù)百倍，或者變慢了數(shù)萬倍。不管數(shù)據(jù)有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具冇0(1)的時間復(fù)雜度，也稱常數(shù)級復(fù)雜度；數(shù)據(jù)規(guī)模變得冇多大，花的時間也跟著變得有多長，這個程序的時間復(fù)雜度就是O(n),比如找n個數(shù)屮的最大值；而像冒泡排序、插入排序等，數(shù)據(jù)擴(kuò)大2倍，吋間變慢4倍的，屬于
3、0(22)的復(fù)雜度。還有一些窮舉類的算法，所盂時間氏度成兒何階數(shù)上漲，這就是0(a5)的指數(shù)級復(fù)雜度，甚至0(n!)的階乘級復(fù)雜度。不會存在0(2^2)的復(fù)雜度，因為前面的那個“2”是系數(shù)，根木不會影響到整個程序的時間增長。同樣地，0(23+22)的復(fù)雜度也就是0(23)的復(fù)雜度。因此我們會說，一個0(0.01*nA3)的程序的效率比O(100*22)的效率低，盡管在n很小的時候，前者優(yōu)于麻者，但示者時間隨數(shù)據(jù)規(guī)模增長得慢，最終0(23)的復(fù)雜度將遠(yuǎn)遠(yuǎn)超過0(22)。我們也說,0(2100)的復(fù)雜度小于0(1.015)的復(fù)雜度。容易看出，前面的幾類復(fù)雜度
4、被分為兩種級別，其中后者的復(fù)雜度無論如何都遠(yuǎn)遠(yuǎn)大于而者：一種是O(l),O(log(n)),O(2a)等，我們把它叫做多項式級的復(fù)雜度，因為它的規(guī)模n出現(xiàn)在底數(shù)的位置；另一種是O(aAn)和O(n!)型復(fù)雜度，它是非多項式級的，其復(fù)雜度計算機(jī)往往不能承受。當(dāng)我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復(fù)雜度，非多項式級的復(fù)雜度需要的時間太多，往往會超時，除非是數(shù)據(jù)規(guī)模非常小。自然地，人們會想到一個問題：會不會所有的問題都可以找到復(fù)雜度為多項式級的算法呢？很遺憾，答案是否定的。冇些問題甚至根本不可能找到一個正確的算法來，這稱Z為“不可解問題"
5、(UndecidableDecisionProblem)0TheHaltingProblem就是一個著名的不可解問題,在我的MSNSpace上有過專門的介紹和證明。再比如，輸出從1到n這n個數(shù)的全排列。不管你用什么方法，你的復(fù)雜度都是階乘級，因為你總得用階乘級的時間打印出結(jié)果來。冇人說，這樣的“問題”不是一個"正規(guī)”的問題，正規(guī)的問題是讓程序解決一個問題，輸出一個“YES”或“NO”(這被稱為判定性問題)，或者一個什么什么的最優(yōu)值(這被稱為最優(yōu)化問題)。那么，根據(jù)這個定義，我也能舉岀一個不大可能會有多項式級算法的問題來：Hamilton回路。問題是這樣的
6、：給你一個圖，問你能否找到一條經(jīng)過每個頂點(diǎn)一次且恰好一次(不遺漏也不重復(fù))最后又走回來的路(滿足這個條件的路徑叫做Hamilton回路)。這個問題現(xiàn)在還沒有找到多項式級的算法。事實(shí)上，這個問題就是我們麻曲要說的NPC問題。下面引入P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。P是英文單詞多項式的第一個字付。哪些問題是P類問題呢？通常NOI和NOIP不會出不屬于P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時I'可的超時程序不會涵蓋任何有價值的算法。接下來
7、引入NP問題的概念。這個就有點(diǎn)難理解了，或者說容易理解錯誤。在這里強(qiáng)調(diào)(回到我竭力想澄清的謀區(qū)上)，NP問題不是非P類問題。吃回題是指可以在多題式的時I'可昱驗誣一個解的回題。一NP」目題的另二個匡義是―可坯庭多項式的吐回黑猜出二個解的迥題.比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準(zhǔn)?，F(xiàn)在某人拿到了一個求最短路徑的問題，問從起點(diǎn)到終點(diǎn)是否有一條小于100個單位長度的路線。它根據(jù)數(shù)據(jù)畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路岀來。然示我就胡亂曲了幾條線，說就這條吧。那人按我指的
8、這條把權(quán)值加起來一看，嘿，神了，路徑長度98,比100小。于是答案出來了，存在比
