怎麼理解 P 問題和 NP 問題？
包括怎麼理解np完全和np hard 問題
P就是能在多項式時間內解決的問題，NP就是能在多項式時間驗證答案正確與否的問題。用大白話講大概就是這樣。所以P是否等於NP實質上就是在問，如果對於一個問題我能在多項式時間內驗證其答案的正確性，那麼我是否能在多項式時間內解決它？這個表述不太嚴謹，但通俗來講就是如此。
再說說NP-hardness和NP-completenes. 這裡涉及一個概念，不妨稱為問題之間的歸約。可以認為各個問題的難度是不同的，表現形式為，如果我可以把問題A中的一個實例轉化為問題B中的一個實例，然後通過解決問題B間接解決問題A，那麼就認為B比A更難。通過對歸約過程做出限制可以得到不同類型的歸約。複雜度理論里經常用到的規約叫polynomial-time Karp" reduction。其要求是轉化問題的過程必須是多項式時間內可計算的。
到這為止NP-hardness和NP-completeness就很好理解了。稱問題L是NP-hard，如果任意一個NP的問題都可以多項式規約到L。如果一個NP-hard的問題L本身就是NP的，則稱L是NP-complete。這個定義可以推廣到所有複雜度類。所以compleness的直觀解釋就是，我能解決這個問題就相當於具備了用相同級別的計算資源解決這個複雜度類里所有問題的能力。05/21/2016 修改： 刪去了「大部分多項式時間演算法都可以簡化成五次冪演算法」，沒有找到依據，添加了到galactic algorithm的鏈接。感謝 @三日月宗近 （知乎的@功能根本點不到重名多的人。。。）
準備寫個詳細點的，為了避免有基礎的看得煩，先簡單來說：
最簡單的解釋：
P：算起來很快的問題NP：算起來不一定快，但對於任何答案我們都可以快速的驗證這個答案對不對NP-hard：比所有的NP問題都難的問題NP-complete：滿足兩點： 1. 是NP hard的問題 2. 是NP問題接下來是比較嚴謹的定義：
問題：對於一個包含由0和1組成的字元串集合S，以某個01字元串x作為輸入，要求某個圖靈機判斷x在不在S裡面。這裡的圖靈機可以先想像成平時我們用的計算機，S也可以被看成我們要解決的問題。注意我們的問題非常簡單，就是要判斷某個字元串x是否在某個集合S裡面，下面是定義：P：有一個圖靈機在多項式時間內能夠判斷x是否在S裡面
NP：有一個圖靈機M，如果某個字元串x在S裡面，那麼存在一個驗證字元串u（注意這個u是針對這個x的，而且長度必須是x長度的多項式好，下面先來解釋為什麼會有人搞出來這麼莫名其妙的定義。這真是說來話長。。。如果想要充分理解整個理論的動機，就逃不開理解圖靈機。
1. 圖靈機是什麼？
想像你只有紙帶和一個類似於打字機一樣的，能夠沿著紙帶寫0或1的自動寫字裝置（只能順著紙帶寫不能跳躍），並且這個機器也能讀在某個位置上的字元是0還是1，現在要求你用這樣一套東西去實現一個演算法，你會怎麼做？observe，這就是計算機發明前數學家們手頭的工具。粗略的說，這就是圖靈機定義的來源。另外我們還需要這個機器能夠記錄它之前做了什麼事情，比如如果用這個機器算100+111，我們需要把紙帶移到個位數，再開始加法，但我們需要及其能夠記住 紙帶已經到個位數 這件事，這樣才能達到自動化，所以這個機器應該能夠保存幾個狀態。這時有個問題：狀態的數目可以根據輸入變化嗎？應該是不可以的，因為如果要機器能夠自動執行某個演算法，我們不希望換個輸入就又要把機器重新製造一遍，這樣簡直比單獨手算每個輸入還麻煩，所以狀態的數量應該是在造機器的時候就定死的（常數）。好奇的同學可能會問：那麼狀態數量就一定不能變化嗎？答案是：如果變化，就不是一個圖靈機模型了；圖靈機只是很多種計算模型的一種，之所以它這麼出名，是因為現代計算機就是一個通用圖靈機，我們天天都在用。比如如果我們允許狀態的數量根據輸入長度變化，那麼這就變成了一個boolean circuit，這個具體是什麼就不展開了。
思考題：能否用上面定義的圖靈機來實現一個簡單的加法器呢？2. 圖靈機為什麼這麼重要？
如上所說，圖靈機只是很多種計算模型中的一種。在計算理論之初，很多數學家提出過很多計算模型，圖靈證明了其它很多計算模型都等價於圖靈機（如果一個問題可以被其他計算模型解決，那麼也可以被圖靈機解決，反之亦然），時間的差距是多項式級別的（簡單的理解為可忽略的差距）如果你做了上面的思考題，那麼對圖靈機的運作模式應該有一定的感覺了。應該可以隱約感受到：所有的演算法都是可以用這樣簡陋的圖靈機實現的。那麼問題來了：有沒有一個圖靈機可以執行所有的演算法呢？這個腦洞來源於：圖靈機本身無非包含紙袋，狀態，字元表（簡單的看成0和1），這樣一個圖靈機當然可以用二進位表示成一串字元，那麼我可以構造一個「超級」圖靈機N，每當我要計算某個問題S，不但把x輸入進去，同時也把某個圖靈機M輸入進去，這個超級圖靈機N就可以根據M的構造模仿M的執行模式，判斷x是否在S裡面。如果這樣一個圖靈機存在，那我們就獲得了可怕的力量：有一個機器可以執行任意可以用圖靈機標識的的演算法了（你的電腦就是這樣一台機器）！
3. 為什麼是多項式時間
對啊為什麼不用指數時間或者常數時間的區別來表示兩個計算模型之間的等價呢，尤其是常數時間看起來更自然啊？比如剛才的加法器，如果你試著多增加幾個狀態，或者不光用01來表示數字，而是用十進位表示數字，你會發現你的計算速度有了多項式時間的提升！在理論體系裡面我們不希望這麼微小的變化就給我們帶來本質上的提升，所以我們用多項式時間定義等價。有的同學可能會問：那很大的多項式怎麼辦？比如幾百次方之類的。。。一般來說常用的多項式演算法（也就是P，能夠被圖靈機在多項式時間內計算），都是低次冪的。然而更合理的解釋是：有的演算法由於有高次冪，所以就不常用了，比如galactic algorithm，有很好的asymptotic behavior，但因為常數項太大所以從未被使用：
Galactic Algorithms實用性和理論研究上確實有不同，理論研究更多的是針對某個計算模型（一般來說就是圖靈積）而講的有效率。4. 關於NP：為什麼驗證一個答案的正確性這麼重要？
因為最開始的時候都是數學家在搞這個，對於數學家來說如果有一個機器能幫助他們證明各種定理那就爽了。數學家經常乾的兩件事：1. 給出證明 2. 驗證某個證明是不是對的。直覺上肯定驗證更容易一些，但如果somehow可以證明NP=P，也就是說 驗證 和 給出證明 其實在數學上是等價的，那麼這個證明很可能給出了如何把 驗證一個證明是否正確（NP）轉化為 如何給出一個證明（P）的方法，從此以後數學家只要思考如何驗證證明的正確性就能自動得到證明了，那不爽炸了。那個時候密碼學的重要性只是嶄露頭角，但即使是在數學上的重要性，也足夠讓這個定義吸引人了。5. 關於NP-complete，為什麼要單獨把NP里最難的問題拿出來
最開始的時候，大家不知道NP的定義是存在所謂 最難的 這麼一個東西的，各類問題沒有固定的比較標準。搞不好就沒有這麼一個最難的東西。直到一個叫Cook的數學家做了點CS的工作，最後還悲慘的沒拿到教職，用教授的話說：「He"s in the wrong department.」 他證明了任何一個NP形式的問題都可以轉換成 3SAT （某個NP問題），3SAT 就是說有n個variable，m個clause，每個clause都是某三個variable 或（|） 在一起， 最後再把所有的clause 和（） 在一起， 問題是：「有沒有一種對於這n個variable的取值可以讓整個boolean formula的值為true？」 3SAT 這個問題的優點在於它非常的直觀清晰。最開始這篇文章沒得到什麼重視，直到一個非常出名的計算機科學家Levin看到了這篇文章，突然意識到如果這麼多問題都等價於 3SAT 問題，那這就很好地揭示了為什麼之前那麼多演算法問題都找不到快速的（多項式級）演算法，因為都和3SAT一樣難嘛；另外可以用 3SAT 作為對各種計算問題的分界線，那以後只要發現是NP-complete的問題，大家就不用對於每個問題找解法了。由此衍生了很多對於complexity class的研究，而cook-levin這種把NP問題化為3SAT的思想一次又一次起到了至關重要的作用。6. 常見誤區：NP=指數級演算法？
不是的。NP強調的是：易於驗證答案的正確性而指數級演算法是指得：存在一個圖靈機可以在指數時間內給出答案如果熟悉了NP的定義，會發現明顯指數級問題包含NP問題（？）因為根據上面的定義，只要驗證對一個輸入x是否存在一個u能夠被某個圖靈機M驗證就好了，那麼在指數時間內，我們可以定義一個hardcode了所有M的信息的圖靈機N，N嘗試所有可能的u，看有沒有哪個u能迫使M接受x。由於u是多項式長度，這種嘗試可以在指數時間內結束。至今為止，我們也只知道NP是包含在指數（EXP）這個class裡面的，但不知道它們相不相等。這也是整個複雜度理論很蛋疼的一點：真包含關係極其難以證明。有的時候真的讓人很懷疑最初的分類方法是不是合理的，究竟是這些問題就沒法被很完美的定義，還是只是我們不夠聰明呢？P類的定義基本上如樓上們所說，確定性 Turing Machine（簡單來說其實就是定義了一個演算法）在多項式時間內可解決的判定問題。具體不再贅述。BTW，Chomsky Hierarchy 真的是個老古董了。。。下面的東西不太嚴謹，不過我嘗試給出一些相對直覺的理解。
NP的話，也不見得非要引入非確定性Turing Machine。舉個例子。想像一下，你和你導師在討論某個東西的證明。你的導師是個學界大牛，而你只是個水平一般的高年級本科生。那麼如何分析你這時候的理解能力呢？有老師帶的時候學習能力真的會變強嘛。。。？
首先嘛，你德高望重的導師當然不希望自己誤人子弟了，所以他會想法設法的說服你，讓你覺得他教你的東西是對的。可是你又是個較真的人，生平最喜歡給比自己厲害的人挑錯了，而且只承認算出來是對的才是對的。。。現在假設你的導師的理解能力是無窮的（不要較真。。。）；而你的理解能力有個上限，因為看的時間長了你很容易困。。那麼比如說就是P類，你在睡著之前可以判斷證明的正確與否。那麼，如果你的導師在扔給你證明（編碼成比特串，下同）之後，就出去旅行了。你（在導師幫助下）要是能理解這個證明，那麼這樣的問題就在NP類里。也就是說，NP類給出的是確定性 Turing Machine在多項式時間內可驗證的判定問題。至於hardness（困難）和completeness（完全），需要用到規約（reduction）的概念。簡單來說，就是如果問題A可以通過一些手段表述成問題B，那麼就認為B至少不比A容易。hardness說的是如果一個complexity class C（一堆問題的集合）可以規約到某些問題的集合D，而且D不見得是C的子集。而completeness的時候，D應該是C的子集（就是求個交）。這裡也不多說了。
話說回來，前面的導師和學生的例子還可以改改。比如說，你把自己有時候（概率大於2/3）看懂的證明就認為是看懂的，而把偶爾（概率小於1/3）看懂的證明不認為看得懂。而且你還是那麼容易困，這時候你能理解證明的水平就是BPP類了。
要是這時候你的導師把證明扔給你之後，還是去旅行了，那麼你（在導師幫助下）的理解能力就是MA類。如果你又向你的導師提了一些問題，而且他看了但是只回復你是或否，你（在導師幫助下）的理解能力就是AM類。如果你的導師真的是德高望重的，換句話說他老人家給了你證明之後不會去旅遊。。。而且允許你提多項式次問題，每次都給答覆。那麼這時候你（在導師幫助下）的理解能力就是IP類（互動式證明系統，Interactive Proofs System）。到這裡都是一堆看起來無聊的定義。不過在92年的時候，Adi Shamir給了個有趣的結果（PSPACE＝IP [1]）：只要證明需要你用的腦容量不是特別大，那麼在你與導師多項式次的討論之後，你總是能看懂證明的！前半句說的「不是特別大的腦容量」，就是說，你的腦容量只夠在你睡著之前記住你讀過的所有證明細節（即Turing Machine使用多項式規模的空間）。很明顯有，因為讀完證明之前你並沒有睡著。
我們還可以考慮你有多個導師，他們共同輔導你看證明的情況，他們扔給你的解釋也可能是多種多樣的（比特串或者是量子態）。。。亦或是雖然他們之間不能通信，但是他們之間可能共享了一組 Bell state 之類有量子糾纏的東西，那麼這個時候你能看懂多難的證明呢？下圖就是你瘋狂的導師們。。。
這裡的「問題」一般形式化為判定問題，如：三班是否有同學刷知乎。
P: 我能在多項式時間內判定三班是否有同學刷知乎。
NP: 我能在多項式時間內判定你給定的某個人（如：王二）是否證明了這個問題（王二在三班且王二刷知乎）。也就是說，對於一個判定性問題，如果其能在多項式時間內得到判定，則是P的；如果能在多項式時間內驗證一個證據（上文中的王二）是否證明出此問題，則其是NP的。這裡又要說道歸約上了。如果A能用多項式次的B解決，稱A能多項式歸約到B。
比如說現在問題A為判定二年級是否有人刷知乎, 那我可以把這個問題規約到問題B:判定每個班級是否有人刷知乎。 只要對二年級所有的班級做一邊問題B，就能得到A的結果，如果這個次數是輸入規模的多項式級別，我們認為A可以多項式規約到B。NP問題有很多種，但若所有的NP問題都能多項式歸約到問題X，X為NP hard，進一步如果X是NP的，稱X是NP complete的。而事實上，的確所有的NP問題都可以規約到某一些NP問題，這類問題也就是經常出現的NP complete問題，比如TSP（旅行商）問題。
一般情況下非判定問題都可以轉化為多項式時間次數的判定問題，所以P和NP的計算複雜度概念可以適用於幾乎所有演算法問題。現在可以知道，由於所有的NP問題都可以多項式規約到某一個NP Complete問題，所以只要一個NP Complete問題能在多項式時間內得到解決，那麼所有的NP問題都可以在多項式時間內得到結局了。目前常見的計算機問題幾乎都是NP的（多項式時間內能驗證結果，大部分演算法問題都滿足），也就是說，如果能多項式解決某一個NP Complete問題，幾乎所有的演算法問題都能在多項式解決了，excited！
雖然願景很美好，但至今並沒有人能證明某個NP Complete問題是P的。而且目前主流的觀點是P不等於NP，當然這也沒有確切的證明。
如果讀到這裡還有興趣，可以參考這個：Chapter 8.5-8.8 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.大致整理過對幾種問題的理解
- 你需要了解的幾個概念(若了解這些概念可以跳過本節):
- 首先，你需要知道什麼是圖靈機模型(Turing Machine - TM): 為了理解的便利，TM可以看作是在計算機「讀/寫」0或1時直接進行工作的部件，實際上它是一個抽象的理想計算模型。在計算的每一時刻，它都處於一個可以用表達式描述的狀態，這個表達式里包括了TM當前的狀態，讀寫頭目前所讀的數，讀寫頭即將在目前位置寫入的數，以及未來讀寫頭的去向(轉移方案)等信息。
- 其次，你需要理解Deterministic TM與Nondeterministic TM的區別: 根據當前狀態和讀寫頭所讀的符號，前者只存在一種狀態轉移方案。而後者存在多種狀態轉移方案，機器將選擇其中一種方案繼續運作，直到最後停機為止。
- 除此之外，所謂A問題規約為B問題是指，B問題是A問題的泛化情況，B問題的解決方法相對於A問題更具有普適性，即B問題的解決方案同樣可以用於解決A問題。
- 最後，你需要明白可以用多項式時間複雜度(polynomial time)的演算法去解決的問題才是我們通常認為的容易解決的問題。
- P問題：可於Deterministic Turing Machine中以多項式時間複雜度的演算法解決，則稱P問題
- 理解：可在多項式時間裡解決的問題。
- NP問題：Nondeterministic Turing Machine中可用多項式時間複雜度的演算法解決，則稱NP問題
- 理解：可在多項式里猜出(驗證)一個解的問題。
- 顯然P問題一定是NP問題，因為任何一個在多項式時間內可以解決的問題一定可以在多項式時間內驗證一個解。(思考Hamilton迴路問題，如果我已經找出了一個解，那麼我一定能在多項式時間內去驗證它是一個有效的解)。
- NPC問題: 存在一個NP問題，使得所有的該類NP問題都可以多項式時間地規約(Polynomial-time Reducibility) 為NPC問題。根據規約的傳遞性，對NP問題進行一層接一層地規約，最終可以得到一個足夠泛化的NP問題，即NPC問題。
- NPC問題本身一定是一個NP問題。
- 如果一個NPC問題可用多項式時間複雜度的演算法去解決，則所有的此類NP問題都可以用這一演算法解決。當然，這一演算法擁有比所有解決該類NP問題的演算法都要高的時間複雜度。
- 如Hamilton迴路問題 (但更多見於邏輯電路問題)。
- NP-Hard問題: 滿足NPC問題定義中的由NP通過規約的條件，但是它本身未必是一個NP問題
首先這些p和np都是用來描述解決一個問題需要的時間和它輸入規模之間的關係...
P問題：一個問題可以在多項式（O(n^k)）的時間複雜度內解決例如：n個數的排序（不超過O(n^2)）
NP問題：
一個問題的解可以在多項式的時間內被證實或證偽例如：典型的子集求和問題,給定一個整數集合求是否存在一個非空子集它的和為零。如給定集合s={-1,3,2,-5,6}，很明顯子集{3,2,-5}能滿足問題，並且驗證該解只需要線性時間複雜度就能被證實。
NP-hard問題：
任意np問題都可以在多項式時間內歸約為該問題。歸約的意思是為了解決問題A，先將問題A歸約為另一個問題B，解決問題B同時也間接解決了問題A。例如，停機問題。
NPC問題：
既是NP問題，也是NP-hard問題。例如，SAT問題（第一個NPC問題）。該問題的基本意思是，給定一系列布爾變數以及它的約束集，是否存在一個解使得它的輸出為真。
相互關係：
顯然，所有P問題都是NP問題，反之則不一定。npc問題是np問題的子集，也是p問題和np問題的差異所在。如果找到一個多項式內能被解決的npc問題的解決方法，那麼P=NP。
看了網上維基百科和這裡幾個高票答案，沒有幾個能講清楚，或者適合原來就適合不懂的人看的。
這篇講的最好http://www.matrix67.com/blog/archives/105P問題的定義是確定型圖靈機在多項式步數給出問題的解,而NP是非確定型圖靈機在多項式時間內給出問題的解,兩個問題的唯一區別就是是否存在不確定性行為.
P和NP,區別就在於確定型圖靈機和非確定型圖靈機了.為啥定義圖靈機呢,而不說自動機,下推機之類的,主要由於它牛叉,可以處理任意可計算的問題.而其他東西都有一定局限性.NP和P就是一個確定一個非確定,還有一定想提的就是P問題屬於NP問題,由於確定型圖靈機屬於不確定型圖靈機(不確定型就是操作的行為不確定,可以用不確定型自動機的概念去理解,但是不確定型圖靈機不等於確定性圖靈機,它們是包含關係).然後什麼又是NP難和NPC問題呢?如果上面的P和NP理解了,這兩個概念也不難理解.NP難就是所有的NP問題都可以在多項式時間規約到問題B(這個"所有"主要是為NPC作鋪墊,只要證明一個NPC問題有P的解法,那麼所有的NP問題都可以多項式時間規約到這個NPC問題,然後NP問題就有P的解法了,然後就得到NP=P),那麼B就是NP難了.那什麼是多項式規約到呢?就是經過一些亂七八糟的操作和變換,但是操作和變換的次數必須是多項式的次數.然後就得到另一個問題B了,這是B就是NP難了,注意這裡B問題沒有說一定是NP問題.B也有可能不是NP問題.那不是NP問題那時啥問題呢?這就更複雜了,可能是那些由非確定型圖靈機也不能在多項式時間處理的問題.那如果B是NP問題呢?那麼我們就可以說B是NPC問題了.那如果B也是P問題呢?這就導出P=NP這個歷史型結論了.但是目前還沒人證明出來.====================================================下面是從文法角度區理解圖靈機的概念. 理解這個首先就得先理解下圖靈機的概念,如果是計算機專業的話應該學過編譯原理,裡面講了0型文法,1型文法,2型文法和3型文法,其中的0型文法就是可以由圖靈機接受的.限制最少的. 這個問題可能還有些抽象,下面我這裡分別敘述下四種文法的區別,方便理解圖靈機的概念. 3型文法是最簡單的,正則文法.由有限自動機接受,基本大家都可以很簡答理解.但是這個文法無法處理一些問題,有一定局限性,比如建議先看計算理論，理解圖靈機模型然後理解複雜度P是確定性圖靈機在多項式時間內可解決的問題，NP是確定性圖靈機在多項式時間內可「驗證」一個解的問題，這個是原始定義，也可以說NP是非確定性圖靈機在多項式時間可解決的問題，兩個定義可證明是等價的之所以推薦先看圖靈機再理解複雜度是因為涉及「偽多項式」複雜度這個問題：偽多項式複雜度
p是多項式時間內用確定的演算法求解的判定問題的集合。NP問題所有可以在多項式問題內用不確定演算法求解的判定問題的集合。
## P、NP、NP-hardness、NP-completeness
- P問題：確定性圖靈機，能在P(Polynomial多項式)複雜度時間內能解決的問題 - NP問題: 非確定圖靈機，能在P複雜度時間內能解決的問題(第一種定義)，也就是能在P複雜度時間內，判斷解的正確性(第二種定義)這兩種定義是相等的，因為第一種定義，可以分為2個階段，第一個階段，用非確定性的方式來生成解，第二個階段，用確定性圖靈機在P複雜度時間來確定解是否正確
- NP"難"問題: 任何一個NP問題，都能在多項式時間內簡化成的某個問題，那麼這個問題就是一個NP"難"問題 - NP完全問題: 一個問題，既是NP問題，又是NP難問題 - 世界級難題之一: 判斷一個明確的NP問題**是否**能在多項式時間複雜度可以被確定性圖靈機解決？(即NP問題是不是一個P問題, NP =? P)NP vs P 問題的歐拉圖表示
花時間讀完這篇文章一定能完全明白：什麼是P問題、NP問題和NPC問題 -by @matrix67同時感謝原作者。
Matrix67原創轉載出處:什麼是P問題、NP問題和NPC問題什麼是P問題、NP問題和NPC問題
這或許是眾多OIer最大的誤區之一。
你會經常看到網上出現「這怎麼做，這不是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就是一個著名的不可解問題，在我的Blog上有過專門的介紹和證明。再比如，輸出從1到n這n個數的全排列。不管你用什麼方法，你的複雜度都是階乘級，因為你總得用階乘級的時間列印出結果來。有人說，這樣的「問題」不是一個「正規」的問題，正規的問題是讓程序解決一個問題，輸出一個「YES」或「NO」（這被稱為判定性問題），或者一個什麼什麼的最優值（這被稱為最優化問題）。那麼，根據這個定義，我也能舉出一個不大可能會有多項式級演算法的問題來：Hamilton迴路。問題是這樣的：給你一個圖，問你能否找到一條經過每個頂點一次且恰好一次（不遺漏也不重複）最後又走回來的路（滿足這個條件的路徑叫做Hamilton迴路）。這個問題現在還沒有找到多項式級的演算法。事實上，這個問題就是我們後面要說的NPC問題。
下面引入P類問題的概念：如果一個問題可以找到一個能在多項式的時間裡解決它的演算法，那麼這個問題就屬於P問題。P是英文單詞多項式的第一個字母。哪些問題是P類問題呢？通常NOI和NOIP不會出不屬於P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時間的超時程序不會涵蓋任何有價值的演算法。
接下來引入NP問題的概念。這個就有點難理解了，或者說容易理解錯誤。在這裡強調（回到我竭力想澄清的誤區上），NP問題不是非P類問題。NP問題是指可以在多項式的時間裡驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間裡猜出一個解的問題。比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準。現在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小於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。現在，所有對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。《演算法導論》上舉了這麼一個例子。比如說，現在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那麼我們說，前者可以約化為後者，意即知道如何解一個一元二次方程那麼一定能解出一元一次方程。我們可以寫出兩個程序分別對應兩個問題，那麼我們能找到一個「規則」，按照這個規則把解一元一次方程程序的輸入數據變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結果。這個規則即是：兩個方程的對應項係數不變，一元二次方程的二次項係數為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├─→┤ └──┘ └─→┤ │ nbsp;└───┘ │ ┌─→┤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問題。現在被證明是NPC問題的有很多，任何一個找到了多項式演算法的話所有的NP問題都可以完美解決了。因此說，正是因為NPC問題的存在，P=NP變得難以置信。P=NP問題還有許多有趣的東西，有待大家自己進一步的挖掘。攀登這個信息學的巔峰是我們這一代的終極目標。現在我們需要做的，至少是不要把概念弄混淆了。
樓上好像沒有人提到過描述複雜度理論……可以用根本不涉及具體計算模型（「確定性或非確定性圖靈機」）或漸近行為（「多項式時間」）的方式來定義P和NP。假如我們不曾發明過計算機也不曾思考過類似的想法，P和NP依然可以被數學家和邏輯學家們發現並賦予其他的含義，它們本質上是從邏輯結構自然產生出來的，無關具體的計算模型。Descriptive complexity theory
NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets.
In the presence of linear order, first-order logic with a least fixed point operator gives P
If P ！= NP
其實關於NP問題的解釋大家都看過，但是就是看過而已。p是多項式時間能夠解決的，NP是多項式時間無法得到結果的。我所理解的就是，其實他們都是可以通過程序來得到最終結果，但是不同的是，在輸入的數量級特別大的時候，那就壞啦，np可能很久很久結果都出不來。npc是np-hard的子集，npc問題都是np-hard（平時證明偷懶，只證明為NP-hard問題）。其實也不是那麼難以理解，首先你要熟悉幾個經典的NP問題(knapsack, job scheduling, cover, TSP, SAT..)，在你遇到一個問題的時候，看看它能否歸約為經典的NP問題，或者對問題的約束變一變，再歸約。最討厭的是這裡還隱藏了一類偽多項式時間的問題，像背包問題的動態規劃解法，其實就是個偽多項式時間解法，實際上卻是NP問題。（解釋的鏈接找不到了）我覺得我們研究NP問題的目的，最終都是為了找到一個多項式時間的近似解法，並證明近似比，進行一定的理論分析，這才是它的重點。（隨性的說了點，不對歡迎指正）
對於一個問題給定一個規模為n的輸入，如果能在n的多項式時間(polynomial time)內解決(即存在多項式時間複雜度的演算法)我們就說這個問題是polynomial time solvable的，簡稱p的，比如排序問題就是p的。那np又是什麼意思呢，似乎每當碰到那種死活找不到p時間演算法的問題時學長就會出來指點說這個問題是np的，np很字面上很容易誤解成沒有p時間演算法，於是在很長一段時間裡都把np問題理解成了很難解決的問題。其實說一個問題是np的恰恰不是說這個問題很難，而且說這個問題很簡單，這個問題有多簡單呢，用非確定性圖靈機在p的時間就能解決(Non-deterministic Turing machine Polynomial time solvable)，那麼問題來了，什麼是非確定性圖靈機呢，目測手機的電是不夠用了，嗯，我們來說點實用的吧，如果學妹來請教你一個問題是不是np的該怎麼辦，首先看看這個問題是不是簡單問題，就是只需回答是和否的問題，剛才說了np問題是一類簡單問題，她和你媽掉水裡了救誰這類問題可比np問題難多了，然後呢，假如我告訴你一個這個問題的答案你看看你能不能快速判斷(能寫出多項式時間的程序)我是不是在忽悠你，如果能快速驗證答案那麼這個問題就是np的了。說了這麼多估計還是很困惑為嘛要搞個p和np出來，唉，that"s a long story，洗洗睡了
看完matrix67大神的解釋來回答：
一切需要從演算法複雜度開始說起，演算法複雜度不是說某個演算法計算需要多少時間，而是衡量當問題的規模增大時，演算法需要的時間會怎麼增加。
例如：
O(n) 是指規模增加多少，演算法時間就增加多少。像是從n個數里找出最小的數，把n個數過一遍就能找到。當n增大1個單位，演算法時間也增加一個單位。
O(n^2)：演算法時間增加的速度是規模增加的速度平方
複雜度包括：
- 多項式複雜度：如O(1), O(n), O(n^a)
- 非多項式複雜度：如O(a^n), O(n!), O(n^n)
那麼，定義：
有多項式複雜度的演算法的問題為P類問題
那麼，沒有多項式複雜度演算法的問題呢？像是旅行商（Travelling salesman problemTSP）問題的變體
給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的路，總路程小於700公里
如果我隨機猜一個答案，給出訪問城市的順序，可以花費多項式時間O(n)驗證這個答案，只要按順序把距離加起來就可以。
那麼，定義
可以在多項式時間驗證一個解的問題為NP問題
定義NP問題的原因在於，我們相信驗證一個解的複雜度不會大於解這個問題的演算法複雜度。所以當驗證解的複雜度都是非多項式時候，相信這個問題沒有多項式複雜度的演算法。
以上就P類問題和NP問題的區別了
matrix67文中也提到了NP-完全問題（NPC 問題）和NP-hard問題，我也概括一下。
首先需要知道約化（Reducibility，也稱歸約）的概念。如果能用問題B的演算法來解決問題A，那麼稱：
問題A可以約化成問題B
例如：解一元二次方程的方法可以解一元一次方程，一元一次方程就可以約化成一元二次方程
可以認為問題B比問題A的難度更大，有更苛刻的條件，維度更高。問題A是問題B的子集。
約化有個重要的性質是傳遞。
於是，我們就想，是否有這樣一個終極問題，全部的問題都可以約化成這個終極問題，只要有辦法解決終極問題，其他問題都能解決。
而NPC問題的含義就是：
如果一個問題是NPC全問題，
那麼，全部的NP問題都可以轉化成這個問題。
當然，這個轉化的時間複雜度必須是多項式的，不然轉化就沒有意義了。
NPC問題的條件是：
1）這是一個NP問題
2）一個已知的NPC問題可以轉化成這個問題
有點像是重複定義的感覺，但是第一個已知的NPC問題是存在的，就是邏輯電路問題，有嚴謹的證明過程，雖然複雜但是並不是不可能（雖然我也沒看...)。
最後，NP-hard問題就是滿足NPC的第二個條件，但是不滿足第一個。也就是說，NP-hard問題像是TSP問題就是沒辦法在多項式時間內驗證解
給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短路
NP-hard問題比NPC問題更加廣泛，維度更高，也更難
參考：
http://www.matrix67.com/blog/archives/105
P和np都是「不是不能在正常時間內可解」的問題（也就是說還有些問題天生就是被證明無解的，但我們的p和np不是）。。
但P是肯定能在正常時間解的問題。
NP是我能驗證這貨能解啊，但是我就是找不到合理時間（比如宇宙毀滅前）的解。
Npc是說np里有這麼一類問題，他們中解一個全部np問題就都有解了為什麼有這麼牛的問題呢？比如說你學過命題邏輯吧，一個命題公式（比如「今天下雨我就不出門」）是不是可判定的（我忘了，亂寫下）就是個npc 問題，為什麼呢，因為所有問題都可以歸約為這個問題，任何問題用命題公式寫出來了就歸約balabala總之就是問題是能互相歸約的，Npc就是幾個np都能歸約過去的問題。不想寫了，你懂的吧。。。某人在有限時間內習得而擁有發展出來的某種特定能力或技能，你能不能通過一個解法而獲得或檢驗其能力和技能的結果。
推薦閱讀：
※FAQ-開發時需要先完成全部詳細設計/類圖嗎，如果需要那要詳細到什麼程度？
※從接觸編程到工作，你們對編程的認識是一個怎樣的變化過程？
※為什麼C語言的Hello,world都是用printf輸出而不是puts？
※C#與VC++在桌面軟體的開發比較?
※一行 JS (以分號結束)能實現什麼喪心病狂的功能？