澄清P問題、NP問題、NPC問題的概念

這或許是眾多OIer最大的誤區之一。

你會經?？吹骄W上出現“這怎么做，這不是NP問題嗎”、“這個只有搜了，這已經被證明是NP問題了”之類的話。你要知道，大多數人此時所說的NP問題其實都是指的NPC問題。他們沒有搞清楚NP問題和NPC問題的概念。NP問題并不是那種“只有搜才行”的問題，NPC問題才是。好，行了，基本上這個誤解已經被澄清了。下面的內容都是在講什么是P問題，什么是NP問題，什么是NPC問題，你如果不是很感興趣就可以不看了。接下來你可以看到，把NP問題當成是NPC問題是一個多大的錯誤。
還是先用幾句話簡單說明一下時間復雜度。時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規模擴大后，程序需要的時間長度增長得有多快。也就是說，對于高速處理數據的計算機來說，處理某一個特定數據的效率不能衡量一個程序的好壞，而應該看當這個數據的規模變大到數百倍后，程序運行時間是否還是一樣，或者也跟著慢了數百倍，或者變慢了數萬倍。不管數據有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具有O(1)的時間復雜度，也稱常數級復雜度；數據規模變得有多大，花的時間也跟著變得有多長，這個程序的時間復雜度就是O(n)，比如找n個數中的最大值；而像冒泡排序、插入排序等，數據擴大2倍，時間變慢4倍的，屬于O(n^2)的復雜度。還有一些窮舉類的算法，所需時間長度成幾何階數上漲，這就是O(a^n)的指數級復雜度，甚至O(n!)的階乘級復雜度。不會存在O(2*n^2)的復雜度，因為前面的那個“2”是系數，根本不會影響到整個程序的時間增長。同樣地，O(n^3+n^2)的復雜度也就是O(n^3)的復雜度。因此，我們會說，一個O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，盡管在n很小的時候，前者優于后者，但后者時間隨數據規模增長得慢，最終O(n^3)的復雜度將遠遠超過O(n^2)。我們也說，O(n^100)的復雜度小于O(1.01^n)的復雜度。
容易看出，前面的幾類復雜度被分為兩種級別，其中后者的復雜度無論如何都遠遠大于前者：一種是O(1),O(log(n)),O(n^a)等，我們把它叫做多項式級的復雜度，因為它的規模n出現在底數的位置；另一種是O(a^n)和O(n!)型復雜度，它是非多項式級的，其復雜度計算機往往不能承受。當我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復雜度，非多項式級的復雜度需要的時間太多，往往會超時，除非是數據規模非常小。
自然地，人們會想到一個問題：會不會所有的問題都可以找到復雜度為多項式級的算法呢？很遺憾，答案是否定的。有些問題甚至根本不可能找到一個正確的算法來，這稱之為“不可解問題”(Undecidable Decision Problem)。The Halting Problem就是一個著名的不可解問題，在我的MSN Space上有過專門的介紹和證明。再比如，輸出從1到n這n個數的全排列。不管你用什么方法，你的復雜度都是階乘級，因為你總得用階乘級的時間打印出結果來。有人說，這樣的“問題”不是一個“正規”的問題，正規的問題是讓程序解決一個問題，輸出一個“YES”或“NO”（這被稱為判定性問題），或者一個什么什么的最優值（這被稱為最優化問題）。那么，根據這個定義，我也能舉出一個不大可能會有多項式級算法的問題來：Hamilton回路。問題是這樣的：給你一個圖，問你能否找到一條經過每個頂點一次且恰好一次（不遺漏也不重復）最后又走回來的路（滿足這個條件的路徑叫做Hamilton回路）。這個問題現在還沒有找到多項式級的算法。事實上，這個問題就是我們后面要說的NPC問題。
下面引入P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。P是英文單詞多項式的第一個字母。哪些問題是P類問題呢？通常NOI和NOIP不會出不屬于P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時間的超時程序不會涵蓋任何有價值的算法。
接下來引入NP問題的概念。這個就有點難理解了，或者說容易理解錯誤。在這里強調（回到我竭力想澄清的誤區上），NP問題不是非P類問題。NP問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準?，F在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小于100個單位長度的路線。它根據數據畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路出來。然后我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權值加起來一看，嘿，神了，路徑長度98，比100小。于是答案出來了，存在比100小的路徑。別人會問他這題怎么做出來的，他就可以說，因為我找到了一個比100小的解。在這個題中，找一個解很困難，但驗證一個解很容易。驗證一個解只需要O(n)的時間復雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。那么，只要我RP好，猜得準，我一定能在多項式的時間里解決這個問題。我猜到的方案總是最優的，不滿足題意的方案也不會來騙我去選它。這就是NP問題。當然有不是NP問題的問題，即你猜到了解但是沒用，因為你不能在多項式的時間里去驗證它。下面我要舉的例子是一個經典的例子，它指出了一個目前還沒有辦法在多項式的時間里驗證一個解的問題。很顯然，前面所說的Hamilton回路是NP問題，因為驗證一條路是否恰好經過了每一個頂點非常容易。但我要把問題換成這樣：試問一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式的時間里進行驗證了，因為除非你試過所有的路，否則你不敢斷定它“沒有Hamilton回路”。
之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的算法。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法。相信讀者很快明白，信息學中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關系。
很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關鍵是，人們想知道，是否所有的NP問題都是P類問題。我們可以再用集合的觀點來說明。如果把所有P類問題歸為一個集合P中，把所有NP問題劃進另一個集合NP中，那么，顯然有P屬于NP?，F在，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？通常所謂的“NP問題”，其實就一句話：證明或推翻P=NP。
NP問題一直都是信息學的巔峰。巔峰，意即很引人注目但難以解決。在信息學研究中，這是一個耗費了很多時間和精力也沒有解決的終極問題，好比物理學中的大統一和數學中的歌德巴赫猜想等。
目前為止這個問題還“啃不動”。但是，一個總的趨勢、一個大方向是有的。人們普遍認為，P=NP不成立，也就是說，多數人相信，存在至少一個不可能有多項式級復雜度的算法的NP問題。人們如此堅信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP-完全問題，也即所謂的NPC問題。C是英文單詞“完全”的第一個字母。正是NPC問題的存在，使人們相信P≠NP。下文將花大量篇幅介紹NPC問題，你從中可以體會到NPC問題使P=NP變得多么不可思議。
為了說明NPC問題，我們先引入一個概念——約化(Reducibility，有的資料上叫“歸約”)。
簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B?！端惴▽д摗飞吓e了這么一個例子。比如說，現在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應兩個問題，那么我們能找到一個“規則”，按照這個規則把解一元一次方程程序的輸入數據變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結果。這個規則即是：兩個方程的對應項系數不變，一元二次方程的二次項系數為0。按照這個規則把前一個問題轉換成后一個問題，兩個問題就等價了。同樣地，我們可以說，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem，旅行商問題)：在Hamilton回路問題中，兩點相連即這兩點距離為0，兩點不直接相連則令其距離為1，于是問題轉化為在TSP問題中，是否存在一條長為0的路徑。Hamilton回路存在當且僅當TSP問題中存在長為0的回路。
“問題A可約化為問題B”有一個重要的直觀意義：B的時間復雜度高于或者等于A的時間復雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間復雜度比A的時間復雜度還低了，那A的算法就可以改進為B的算法，兩者的時間復雜度還是相同。正如解一元二次方程比解一元一次方程難，因為解決前者的方法可以用來解決后者。
很顯然，約化具有一項重要的性質：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。這個道理非常簡單，就不必闡述了。
現在再來說一下約化的標準概念就不難理解了：如果能找到這樣一個變化法則，對任意一個程序A的輸入，都能按這個法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說，問題A可約化為問題B。
當然，我們所說的“可約化”是指的可“多項式地”約化(Polynomial-time Reducible)，即變換輸入的方法是能在多項式的時間里完成的。約化的過程只有用多項式的時間完成才有意義。
  好了，從約化的定義中我們看到，一個問題約化為另一個問題，時間復雜度增加了，問題的應用范圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找復雜度更高，但應用范圍更廣的算法來代替復雜度雖然低，但只能用于很小的一類問題的算法。再回想前面講的P和NP問題，聯想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復雜的大NP問題，那么最后是否有可能找到一個時間復雜度最高，并且能“通吃”所有的NP問題的這樣一個超級NP問題？答案居然是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。這種問題的存在難以置信，并且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是傳說中的NPC問題，也就是NP-完全問題。NPC問題的出現使整個NP問題的研究得到了飛躍式的發展。我們有理由相信，NPC問題是最復雜的問題。再次回到全文開頭，我們可以看到，人們想表達一個問題不存在多項式的高效算法時應該說它“屬于NPC問題”。此時，我的目的終于達到了，我已經把NP問題和NPC問題區別開了。到此為止，本文已經寫了近5000字了，我佩服你還能看到這里來，同時也佩服一下自己能寫到這里來。
   NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然后，所有的NP問題都可以約化到它。證明一個問題是NPC問題也很簡單。先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足；至于第一個NPC問題是怎么來的，下文將介紹），這樣就可以說它是NPC問題了。
   既然所有的NP問題都能約化成NPC問題，那么只要任意一個NPC問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了，NP也就等于P了。因此，給NPC找一個多項式算法太不可思議了。因此，前文才說，“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效算法，只能用指數級甚至階乘級復雜度的搜索。

順便講一下NP-Hard問題。NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比NPC問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發現了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復雜度更高從而更難以解決。

不要以為NPC問題是一紙空談。NPC問題是存在的。確實有這么一個非常具體的問題屬于NPC問題。下文即將介紹它。

下文即將介紹邏輯電路問題。這是第一個NPC問題。其它的NPC問題都是由這個問題約化而來的。因此，邏輯電路問題是NPC類問題的“鼻祖”。

邏輯電路問題是指的這樣一個問題：給定一個邏輯電路，問是否存在一種輸入使輸出為True。

什么叫做邏輯電路呢？一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成?？聪旅嬉焕?，不需要解釋你馬上就明白了。

 ┌───┐
 │ 輸入1├─→┐    ┌──┐
 └───┘    └─→┤    │
                    │ OR ├→─┐
 ┌───┐    ┌─→┤    │    │    ┌──┐
 │ 輸入2├─→┤    └──┘    └─→┤    │
 └───┘    │               ┌─→┤AND ├──→輸出
              └────────┘ ┌→┤    │
 ┌───┐    ┌──┐            │  └──┘
 │ 輸入3├─→┤ NOT├─→────-┘
 └───┘    └──┘

這是個較簡單的邏輯電路，當輸入1、輸入2、輸入3分別為True、True、False或False、True、False時，輸出為True。

有輸出無論如何都不可能為True的邏輯電路嗎？有。下面就是一個簡單的例子。

 ┌───┐
 │輸入1 ├→─┐    ┌──┐
 └───┘    └─→┤    │
                    │AND ├─→┐
              ┌─→┤    │    │
              │    └──┘    │  ┌──┐
              │               └→┤    │
 ┌───┐    │                   │AND ├─→輸出
 │輸入2 ├→─┤  ┌──┐      ┌→┤    │
 └───┘    └→┤NOT ├→──┘  └──┘
                  └──┘

上面這個邏輯電路中，無論輸入是什么，輸出都是False。我們就說，這個邏輯電路不存在使輸出為True的一組輸入。

回到上文，給定一個邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。

邏輯電路問題屬于NPC問題。這是有嚴格證明的。它顯然屬于NP問題，并且可以直接證明所有的NP問題都可以約化到它（不要以為NP問題有無窮多個將給證明造成不可逾越的困難）。證明過程相當復雜，其大概意思是說任意一個NP問題的輸入和輸出都可以轉換成邏輯電路的輸入和輸出（想想計算機內部也不過是一些0和1的運算），因此對于一個NP問題來說，問題轉化為了求出滿足結果為True的一個輸入（即一個可行解）。

有了第一個NPC問題后，一大堆NPC問題就出現了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了。后來，Hamilton回路成了NPC問題，TSP問題也成了NPC問題?，F在被證明是NPC問題的有很多，任何一個找到了多項式算法的話所有的NP問題都可以完美解決了。因此說，正是因為NPC問題的存在，P=NP變得難以置信。P=NP問題還有許多有趣的東西，有待大家自己進一步的挖掘。攀登這個信息學的巔峰是我們這一代的終極目標?，F在我們需要做的，至少是不要把概念弄混淆了。

--------------------------------------------------------------------------

1、有解但無算法的問題：

比如圓周率Pi的小數點后面是否有連續的100萬個0。因為Pi是一個客觀存在的實數，所以Pi的值是確定的，因此這個問題的解也是存在的。要么是yes,要么是no，雖然我們不知道他到底是什么，但他是客觀存在的，不隨時間改變，不隨人的認識而改變。但是沒有算法可以計算這個問題的答案。當然，可以用一種苯辦法來解決這個問題，就是不停地計算Pi的小數點后面的值，如果發現了有連續的100萬個0，則這個問題的答案就是yes，但是如果沒有發現，我們必須一直計算下去，而且永遠無法停止~~，所以這種苯辦法根本稱不上是算法，因為他不滿足算法在有限步內終止的條件。所以這個問題是沒有算法的（至少目前認為如此，也許以后可以從數論中找到某種方法來求出小數點后面是否有連續的k個0，或從概率的角度計算Pi的小數點后面的值的分布等等等等）。

2、無解也無算法的問題：

例如，給定任意一個命題，是否存在一種算法判斷這個命題是真是假？這就是著名的圖靈停機問題。如果存在這個算法，那么我們只要找到這個算法就可以一勞永逸了，以后無論拿到什么新的命題，都可以用這個算法來驗證一下，立刻就知道該命題是真是假，這樣我們就掌握了整個宇宙的終極真理：）。但是圖靈已經證明了這樣的算法是不存在的，這個問題也是無解的。（證明中主要利用了康托爾對角線刪除法，就是用來證明實數和自然數不等勢的那種對角線刪除法）

3、可計算與不可計算：

根據圖靈-丘奇論題，：

1、可計算的問題就是能被圖靈機計算的問題；（圖靈的定義）
2、可計算的問題就是使用lamda演算系統可以計算的問題；(丘奇的定義)
圖靈丘奇論題與其說是定理，不如說是算法的定義。因為算法本身就是一個不精確的概念，到底什么是算法，以前一直沒有確切的定義。而圖靈-丘奇論題則從數學上給出了算法的形式定義。

圖靈說：所有的圖靈機能計算的問題都是有算法的（也就是可計算的），所有有算法的問題都可以用圖靈機計算。這個論題本身是無法證明的，它就像物理中的光速不變定律一樣，是一條自然定律，不能加以邏輯上的證明，只能用實驗來檢驗。而目前來看，圖靈命題也和光速不變一樣，經得住歷史和時間的檢驗，現在即使發展到了量子計算機，還是沒有擺脫圖靈機的約束，量子計算機上可計算的問題也是普通的圖靈機上可計算的問題，只不過計算效率不同而已。

不可計算的問題的兩個例子前面已經說過了，一個是Pi的例子，另一個是圖靈停機問題。

4、可證明性與不可證明性

在一個公里系統中，有若干條公里，有一些推導規則，在系統中進行定理的證明，就是從公理出發，利用這些規則推導出新的定理。如果最終能得到我們需要證明的命題，則該命題為真；如果最終得到了和我們需要證明的命題相違背的命題，則我們要證明的命題為假。

如果把系統中所有的定理看作圖中的節點，假如從定理i1,i2,..ik根據系統的規則可以推導出定理j，則從i1,i2,...ik分別連接一條到j的有向邊。這樣整個公理系統構造成了一個有向圖。定理的證明過程事實上是在公理系統中從公理表示的節點出發，構造一顆到達目標命題節點的“證明樹”。因而定理的證明就和圖論中的路經搜索類似（BTW，這就是定理自動化證明的基本原理）。

超級天才歌德爾在25歲的時候提出了著名的歌德爾不完備性定理。該定理指出：在任何一個公理化系統中，要么存在著矛盾，這個系統是不完備的。
所謂存在著矛盾，就是可以證明命題A成立，也可以證明命題A的否命題成立，這就自相矛盾了。
所謂不完備，是指系統中存在著一些命題，無法證明它成立，也無法證明它不成立。這就好像在一個圖中存在著某些孤立點，從基本的公理節點出發永遠無法訪問到這些孤立點。

歌德爾在“不完備性定理”的證明過程中構造出了一個無法證明是真是偽的定理。具體說起來比較麻煩，我根據自己的理解將其簡化為下述的簡單形式：

命題A = “命題A不成立”

現在問命題A是否成立。如果命題A成立，則根據命題A的內容，命題A應該不成立；如果命題A不成立，則根據命題A的內容，命題A又應該成立。

這個例子很不嚴謹，因為它事實上混淆了語法和語義層次。但我覺得這個例子可以作為歌德爾的例子的一個簡化版本。歌德的那個例子要比這個嚴謹和復雜得多，但實質上是差不多的，也是利用了邏輯中的悖論。

羅素等人所提倡的解決這種悖論的方法就是給謂詞邏輯分層次，從而產生了一階謂詞邏輯、二階謂詞邏輯等。像上面的例子，羅素認為命題A的內容描述了命題A本身的性質，這就超出了命題A所能表達的范圍，他認為這樣的A不是合法的命題。