什么是P問題、NP問題和NPC問題

先用幾句話簡(jiǎn)單說明一下時(shí)間復(fù)雜度時(shí)間復(fù)雜度并不是表示一個(gè)程序解決問題需要花多少時(shí)間，而是當(dāng)問題規(guī)模擴(kuò)大后，程序需要的時(shí)間長(zhǎng)度增長(zhǎng)得有多快。也就是說，對(duì)于高速處理數(shù)據(jù)的計(jì)算機(jī)來(lái)說，處理某一個(gè)特定數(shù)據(jù)的效率不能衡量一個(gè)程序的好壞，而應(yīng)該看當(dāng)這個(gè)數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運(yùn)行時(shí)間是否還是一樣，或者也跟著慢了數(shù)百倍，或者變慢了數(shù)萬(wàn)倍。不管數(shù)據(jù)有多大，程序處理花的時(shí)間始終是那么多的，我們就說這個(gè)程序很好，具有O(1)的時(shí)間復(fù)雜度，也稱常數(shù)級(jí)復(fù)雜度；先用幾句話簡(jiǎn)單說明一下時(shí)間復(fù)雜度數(shù)據(jù)規(guī)模變得有多大，花的時(shí)間也跟著變得有多長(zhǎng)，這個(gè)程序的時(shí)間復(fù)雜度就是O(n)，比如找n個(gè)數(shù)中的最大值；而像冒泡排序、插入排序等，數(shù)據(jù)擴(kuò)大2倍，時(shí)間變慢4倍的，屬于O(n^2)的復(fù)雜度。還有一些窮舉類的算法，所需時(shí)間長(zhǎng)度成幾何階數(shù)上漲，這就是O(a^n)的指數(shù)級(jí)復(fù)雜度，甚至O(n!)的階乘級(jí)復(fù)雜度。不會(huì)存在O(2*n^2)的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)“2”是系數(shù)，根本不會(huì)影響到整個(gè)程序的時(shí)間增長(zhǎng)。先用幾句話簡(jiǎn)單說明一下時(shí)間復(fù)雜度同樣地，O(n^3+n^2)的復(fù)雜度也就是O(n^3)的復(fù)雜度。因此，我們會(huì)說，一個(gè)O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，盡管在n很小的時(shí)候，前者優(yōu)于后者，但后者時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)得慢，最終O(n^3)的復(fù)雜度將遠(yuǎn)遠(yuǎn)超過O(n^2)。我們也說，O(n^100)的復(fù)雜度小于O(1.01^n)的復(fù)雜度。先用幾句話簡(jiǎn)單說明一下時(shí)間復(fù)雜度容易看出，前面的幾類復(fù)雜度被分為兩種級(jí)別，其中后者的復(fù)雜度無(wú)論如何都遠(yuǎn)遠(yuǎn)大于前者：一種是O(1),O(log(n)),O(n^a)等，我們把它叫做多項(xiàng)式級(jí)的復(fù)雜度，因?yàn)樗囊?guī)模n出現(xiàn)在底數(shù)的位置；另一種是O(a^n)和O(n!)型復(fù)雜度，它是非多項(xiàng)式級(jí)的，其復(fù)雜度計(jì)算機(jī)往往不能承受。當(dāng)我們?cè)诮鉀Q一個(gè)問題時(shí)，我們選擇的算法通常都需要是多項(xiàng)式級(jí)的復(fù)雜度，非多項(xiàng)式級(jí)的復(fù)雜度需要的時(shí)間太多，往往會(huì)超時(shí)，除非是數(shù)據(jù)規(guī)模非常小。不可解問題

自然地，人們會(huì)想到一個(gè)問題：會(huì)不會(huì)所有的問題都可以找到復(fù)雜度為多項(xiàng)式級(jí)的算法呢？答案是否定的。有些問題甚至根本不可能找到一個(gè)正確的算法來(lái)，這稱之為“不可解問題”(UndecidableDecisionProblem)。例如：

Hamilton回路。問題是這樣的：給你一個(gè)圖，問你能否找到一條經(jīng)過每個(gè)頂點(diǎn)一次且恰好一次（不遺漏也不重復(fù)）最后又走回來(lái)的路（滿足這個(gè)條件的路徑叫做Hamilton回路）。這個(gè)問題現(xiàn)在還沒有找到多項(xiàng)式級(jí)的算法。事實(shí)上，這個(gè)問題就是我們后面要說的NPC問題。P類問題如果一個(gè)問題可以找到一個(gè)能在多項(xiàng)式的時(shí)間里解決它的算法，那么這個(gè)問題就屬于P問題。P是英文單詞多項(xiàng)式的第一個(gè)字母。

NP問題在這里強(qiáng)調(diào)，NP問題不是非P類問題。NP問題是指可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問題。NP問題的另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的問題。

比方說，我RP很好，在程序中需要枚舉時(shí)，我可以一猜一個(gè)準(zhǔn)?，F(xiàn)在某人拿到了一個(gè)求最短路徑的問題，問從起點(diǎn)到終點(diǎn)是否有一條小于100個(gè)單位長(zhǎng)度的路線。它根據(jù)數(shù)據(jù)畫好了圖，但怎么也算不出來(lái)，于是來(lái)問我：你看怎么選條路走得最少？NP問題我說，我RP很好，肯定能隨便給你指條很短的路出來(lái)。然后我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權(quán)值加起來(lái)一看，嘿，神了，路徑長(zhǎng)度98，比100小。于是答案出來(lái)了，存在比100小的路徑。別人會(huì)問他這題怎么做出來(lái)的，他就可以說，因?yàn)槲艺业搅艘粋€(gè)比100小的解。在這個(gè)題中，找一個(gè)解很困難，但驗(yàn)證一個(gè)解很容易。驗(yàn)證一個(gè)解只需要O(n)的時(shí)間復(fù)雜度，也就是說我可以花O(n)的時(shí)間把我猜的路徑的長(zhǎng)度加出來(lái)。那么，只要我RP好，猜得準(zhǔn)，我一定能在多項(xiàng)式的時(shí)間里解決這個(gè)問題。我猜到的方案總是最優(yōu)的，不滿足題意的方案也不會(huì)來(lái)騙我去選它。這就是NP問題。NP問題當(dāng)然有不是NP問題的問題，即你猜到了解但是沒用，因?yàn)槟悴荒茉诙囗?xiàng)式的時(shí)間里去驗(yàn)證它。一個(gè)經(jīng)典的例子，它指出了一個(gè)目前還沒有辦法在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問題。很顯然，前面所說的Hamilton回路是NP問題，因?yàn)轵?yàn)證一條路是否恰好經(jīng)過了每一個(gè)頂點(diǎn)非常容易。但我要把問題換成這樣：試問一個(gè)圖中是否不存在Hamilton回路。這樣問題就沒法在多項(xiàng)式的時(shí)間里進(jìn)行驗(yàn)證了，因?yàn)槌悄阍囘^所有的路，否則你不敢斷定它“沒有Hamilton回路”。NP問題之所以要定義NP問題，是因?yàn)橥ǔＶ挥蠳P問題才可能找到多項(xiàng)式的算法。我們不會(huì)指望一個(gè)連多項(xiàng)式地驗(yàn)證一個(gè)解都不行的問題存在一個(gè)解決它的多項(xiàng)式級(jí)的算法。很顯然，所有的P類問題都是NP問題。也就是說，能多項(xiàng)式地解決一個(gè)問題，必然能多項(xiàng)式地驗(yàn)證一個(gè)問題的解——既然正解都出來(lái)了，驗(yàn)證任意給定的解也只需要比較一下就可以了。NP問題關(guān)鍵是，人們想知道，是否所有的NP問題都是P類問題。

所有對(duì)NP問題的研究都集中在一個(gè)問題上，即究竟是否有P=NP？

目前為止這個(gè)問題還“啃不動(dòng)”。但是，一個(gè)總的趨勢(shì)、一個(gè)大方向是有的。人們普遍認(rèn)為，P=NP不成立，也就是說，多數(shù)人相信，存在至少一個(gè)不可能有多項(xiàng)式級(jí)復(fù)雜度的算法的NP問題。

NPC問題人們?nèi)绱藞?jiān)信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP-完全問題，也即所謂的NPC問題。C是英文單詞“完全”的第一個(gè)字母。正是NPC問題的存在，使人們相信P≠NP。為了說明NPC問題，我們先引入一個(gè)概念——約化(Reducibility，有的資料上叫“歸約”)約化一個(gè)問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。

“問題A可約化為問題B”有一個(gè)重要的直觀意義：B的時(shí)間復(fù)雜度高于或者等于A的時(shí)間復(fù)雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來(lái)解決，倘若B的時(shí)間復(fù)雜度比A的時(shí)間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時(shí)間復(fù)雜度還是相同。約化約化具有一項(xiàng)重要的性質(zhì)：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。約化的標(biāo)準(zhǔn)概念：如果能找到這樣一個(gè)變化法則，對(duì)任意一個(gè)程序A的輸入，都能按這個(gè)法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說，問題A可約化為問題B。我們所說的“可約化”是指的可“多項(xiàng)式地”約化(Polynomial-timeReducible)，即變換輸入的方法是能在多項(xiàng)式的時(shí)間里完成的。約化的過程只有用多項(xiàng)式的時(shí)間完成才有意義。

NPC問題NPC問題的定義非常簡(jiǎn)單。同時(shí)滿足下面兩個(gè)條件的問題就是NPC問題。首先，它得是一個(gè)NP問題；然后，所有的NP問題都可以約化到它。證明一個(gè)問題是NPC問題也很簡(jiǎn)單。先證明它至少是一個(gè)NP問題，再證明其中一個(gè)已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足；至于第一個(gè)NPC問題是怎么來(lái)的，下文將介紹），這樣就可以說它是NPC問題了。NPC問題既然所有的NP問題都能約化成NPC問題，那么只要任意一個(gè)NPC問題找到了一個(gè)多項(xiàng)式的算法，那么所有的NP問題都能用這個(gè)算法解決了，NP也就等于P了。因此前文才說，“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。NP-Hard問題

NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條即NP-Hard問題要比NPC問題的范圍廣。NPC問題NPC問題是存在的。確實(shí)有這么一個(gè)非常具體的問題屬于NPC問題。邏輯電路問題是NPC類問題的“鼻祖”。是第一個(gè)NPC問題。其它的NPC問題都是由這個(gè)問題約化而來(lái)的。邏輯電路問題是指的這樣一個(gè)問題：給定一個(gè)邏輯電路，問是否存在一種輸入使輸出為True。邏輯電路問題邏輯電路問題屬于NPC問題。這是有嚴(yán)格證明的。它顯然屬于NP問題，并且可以直接證明所有的NP問題都可以約化到它。證明過程相當(dāng)復(fù)雜，其大概意思是說任意一個(gè)NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計(jì)算機(jī)內(nèi)部也不過是一些0