前言
P/NP/NPC問題在2012年左右曾經火了一陣，如果你做過2012年和2013年的提高組真題的話，你會發現，那兩年每年都有一道這種問題的多選題。（不過之後就涼涼了），所以這類問題還是有必要了解一下的。 反正重要的知識點就這麼幾句話，我都劃重點了，其他都是瞎扯可以無視的啦QAQ（這句不是重點啊）
零、預備內容：時間複雜度
時間複雜度分為兩種：多項式級複雜度和非多項式級複雜度 其中多項式級複雜度是指規模 n 在底數位置上的或者常數級的複雜度 比如說 O(1) 、 O(n) 、 O(nlogn) 或者 O(n^2) 等等 而非多項式級複雜度則是規模 n 在指數位置上的複雜度 比如說 O(2^n) 或者 O(n!)
這麼區分的原因是因為這兩種複雜度是天差地別的，後者遠大於前者。 舉個例子：當 n=10 的時候
一、P問題的引入
自從發現了這兩種複雜度之後，有些人就開始想了：「多項式複雜度好棒棒啊！如果所有問題都有多項式複雜度的解法就好了啊！」 這個時候，圖靈跳了出來，丟了一個停機問題，人們吃驚地發現，這個問題甚至沒有正確的解決方法，於是上面的flag就這樣子GG了。 所以又有人來說了：「那能解的問題是不是一定有多項式解法呢？」 於是又來了一個問題：請解決3-SAT問題。 然後不用想了，又GG了。 這個時候臉被打得生疼的科學家們發現，他們有必要劃分一下這些問題，以免再被打臉，因此他們就提出了P問題(Polynomial problem)(P是多項式的簡寫)
定義P問題為存在多項式複雜度算法的問題。
二、NP問題的引入
有了P問題，科學家想了想，那我們就搞個不是P問題的專有名詞，專指找不到多項式複雜度的問題（非P問題）不就行了嗎？ 然後他們就提出了NP問題，全劇終 （霧嗯，事情沒有這麼簡單，如果你要向上面那樣想，你就可能要涼涼了。
NP問題不是非P問題
上面那種NP問題的定義會變得非常爆炸，因為你有時候並不能證明這個問題是不是一定沒有多項式解，也就是說不確定現在這個不存在多項式複雜度的問題在未來也不存在多項式複雜度解法，顯然這些問題你既不能歸入P又不能歸入NP，所以你還要再定義一個別的東西來表示他們，反正這個定義GG了
回顧之前所說，我們一開始的希望是找到多項式複雜度的解法，接著才會去考慮劃分這些問題，所以我們的劃分理應去往這個方向靠。
那麼可以將NP問題定義為還不存在多項式複雜度解法的問題，用未解代替無解.(這體現了定義的科學性、準確性、嚴謹性、平實性、周密性)
以及我們的目標是找到NP問題的多項式解法，所以我們要使NP問題有可能能解，顯然要去掉所有能證明無多項式解的問題，如果一個問題的一個解的驗證都是非多項式級別的，這個問題就不可能做到多項式級複雜度，因為如果我們連它的一個條件都無法在多項式複雜度中證明，那麼就更別談在多項式複雜度中把他的所有條件都證明出來了。
終於可以給出NP問題(Non-deterministic Polynomial problem)的完全定義了(沒錯，這個N是不確定的意思)
一個問題的一個解可以用多項式級複雜度檢驗，它就是NP問題
所以有一點值得注意的
找不到多項式複雜度解的(非P問題)不一定是NP問題
因為有些無法在多項式複雜度中檢驗一個解的問題存在。
同時，這裡可以很明顯的發現，如果一個問題是P問題，那麼他肯定能在多項式時間複雜度內檢驗任意一組解。於是又可以推出
P∈NP
但是P=NP嗎？這是一個世紀難題，反正了解一下有這個問題就行了，初賽不會讓你證明的，放心好了。
三、NP-hard和NPC問題的引入
雖然說不用讓你去證明P=NP這種鬼畜的東西，但是科學家不斷嘗試證明的這段歷史是沒準會考的。(畢竟這是一種自強不息的求索精神，很符合二十四字核心價值觀)
在此之前我們先引入歸約的定義
歸約指的是將A問題進行歸約後可以用B問題的解決方法解決，也就是把A問題變成B問題解決
NPhard問題是指
如果有一個問題可以使所有NP問題在多項式複雜度內歸約到它，那麼它就是NP-hard問題
顯然如果難度有一個上界的話，解決所有的NP問題歸約起來的問題難度肯定就是那個上界，所以這類問題被稱為NP-hard。
如果你有了解過停機問題的話，會知道這個問題是不可判的，但是如果把問題理解成輸入一個東西到某個程序裡，判斷他是否會停機，就可以把所有NP問題歸約到停機問題上來，所以停機問題是NP-hard，於是
NP-hard問題不一定是NP問題
既然不一定是NP問題那麼對我們解決P=NP就沒啥用了。 所以科學家又提出了NPC問題：
一個NP問題可以使所有NP問題在多項式複雜度內歸約到它，那麼它就是NPC問題
也就是說如果解決了NPC問題就可以解決所有的NP問題，然後就可以證明P=NP。
常見的NPC問題有3-SAT問題，旅行商問題等等。 這些的證明有興趣大家可以研究一下。最後祭上這張圖來總結上面知識點之間的聯繫
接著我們來切幾道真題。
四、歷年真題
2012.20．以下關於計算複雜度的說法中，正確的有（ ）。 A．如果一個問題不存在多項式時間的算法，那它一定是NP類問題 B．如果一個問題不存在多項式時間的算法，那它一定不是P類問題 C．如果一個問題不存在多項式空間的算法，那它一定是NP類問題 D．如果一個問題不存在多項式空間的算法，那它一定不是P類問題
解析： A 還記得圖靈停機問題嗎？那是一個NP-hard而不是NP問題 B 這是對的，因為P問題的定義是存在多項式時間的複雜度算法 C、D 時間複雜度和空間複雜度都是複雜度，是等價的。
所以選BD
2013.14. （ ）屬於 NP 類問題。 A. 存在一個 P 類問題 B. 任何一個 P 類問題 C. 任何一個不屬於 P 類的問題 D. 任何一個在（輸入規模的）指數時間內能夠解決的問題
解析：這裡考察的知識點是NP問題的定義以及P∈NP 由之前可知任何P問題都是NP問題，同理一定存在一個P問題是NP問題AB都是對的C的話我們可以繼續用萬能的停機問題去反駁他 D考察的是定義，指數時間內能解決不意味著多項式時間能驗證解，所以D是錯的
所以選AB
那就這樣子了，希望對大家有所幫助。
本文發布於洛穀日報，特約作者：Styx
原文地址：https://www.luogu.org/blog/styx-ferryman/chu-sai-bei-kao-gan-huo-p-wen-ti-np-wen-ti-npc-wen-ti-sha-sha-fen-fou