前言

　　P/NP/NPC問(wèn)題在2012年左右曾經(jīng)火了一陣，如果你做過(guò)2012年和2013年的提高組真題的話，你會(huì)發(fā)現(xiàn)，那兩年每年都有一道這種問(wèn)題的多選題。（不過(guò)之后就涼涼了），所以這類問(wèn)題還是有必要了解一下的。
反正重要的知識(shí)點(diǎn)就這么幾句話，我都劃重點(diǎn)了，其他都是瞎扯可以無(wú)視的啦QAQ（這句不是重點(diǎn)?。?/p>

　　零、預(yù)備內(nèi)容：時(shí)間復(fù)雜度

　　時(shí)間復(fù)雜度分為兩種：多項(xiàng)式級(jí)復(fù)雜度和非多項(xiàng)式級(jí)復(fù)雜度
其中多項(xiàng)式級(jí)復(fù)雜度是指規(guī)模 n 在底數(shù)位置上的或者常數(shù)級(jí)的復(fù)雜度
比如說(shuō) O(1) 、 O(n) 、 O(nlogn) 或者 O(n^2) 等等
而非多項(xiàng)式級(jí)復(fù)雜度則是規(guī)模 n 在指數(shù)位置上的復(fù)雜度
比如說(shuō) O(2^n) 或者 O(n!)

　　這么區(qū)分的原因是因?yàn)檫@兩種復(fù)雜度是天差地別的，后者遠(yuǎn)大于前者。
舉個(gè)例子：當(dāng) n=10 的時(shí)候

　　一、P問(wèn)題的引入

　　自從發(fā)現(xiàn)了這兩種復(fù)雜度之后，有些人就開始想了：“多項(xiàng)式復(fù)雜度好棒棒??！如果所有問(wèn)題都有多項(xiàng)式復(fù)雜度的解法就好了啊！”
這個(gè)時(shí)候，圖靈跳了出來(lái)，丟了一個(gè)停機(jī)問(wèn)題，人們吃驚地發(fā)現(xiàn)，這個(gè)問(wèn)題甚至沒有正確的解決方法，于是上面的flag就這樣子GG了。
所以又有人來(lái)說(shuō)了：“那能解的問(wèn)題是不是一定有多項(xiàng)式解法呢？”
于是又來(lái)了一個(gè)問(wèn)題：請(qǐng)解決3-SAT問(wèn)題。
然后不用想了，又GG了。
這個(gè)時(shí)候臉被打得生疼的科學(xué)家們發(fā)現(xiàn)，他們有必要?jiǎng)澐忠幌逻@些問(wèn)題，以免再被打臉，因此他們就提出了P問(wèn)題(Polynomial problem)(P是多項(xiàng)式的簡(jiǎn)寫)

　　定義P問(wèn)題為存在多項(xiàng)式復(fù)雜度算法的問(wèn)題。

　　二、NP問(wèn)題的引入

　　有了P問(wèn)題，科學(xué)家想了想，那我們就搞個(gè)不是P問(wèn)題的專有名詞，專指找不到多項(xiàng)式復(fù)雜度的問(wèn)題（非P問(wèn)題）不就行了嗎？
然后他們就提出了NP問(wèn)題，全劇終 （霧
嗯，事情沒有這么簡(jiǎn)單，如果你要向上面那樣想，你就可能要涼涼了。

　　NP問(wèn)題不是非P問(wèn)題

　　上面那種NP問(wèn)題的定義會(huì)變得非常爆炸，因?yàn)槟阌袝r(shí)候并不能證明這個(gè)問(wèn)題是不是一定沒有多項(xiàng)式解，也就是說(shuō)不確定現(xiàn)在這個(gè)不存在多項(xiàng)式復(fù)雜度的問(wèn)題在未來(lái)也不存在多項(xiàng)式復(fù)雜度解法，顯然這些問(wèn)題你既不能歸入P又不能歸入NP，所以你還要再定義一個(gè)別的東西來(lái)表示他們，反正這個(gè)定義GG了

　　回顧之前所說(shuō)，我們一開始的希望是找到多項(xiàng)式復(fù)雜度的解法，接著才會(huì)去考慮劃分這些問(wèn)題，所以我們的劃分理應(yīng)去往這個(gè)方向靠。

　　那么可以將NP問(wèn)題定義為還不存在多項(xiàng)式復(fù)雜度解法的問(wèn)題，用未解代替無(wú)解.(這體現(xiàn)了定義的科學(xué)性、準(zhǔn)確性、嚴(yán)謹(jǐn)性、平實(shí)性、周密性)

　　以及我們的目標(biāo)是找到NP問(wèn)題的多項(xiàng)式解法，所以我們要使NP問(wèn)題有可能能解，顯然要去掉所有能證明無(wú)多項(xiàng)式解的問(wèn)題，如果一個(gè)問(wèn)題的一個(gè)解的驗(yàn)證都是非多項(xiàng)式級(jí)別的，這個(gè)問(wèn)題就不可能做到多項(xiàng)式級(jí)復(fù)雜度，因?yàn)槿绻覀冞B它的一個(gè)條件都無(wú)法在多項(xiàng)式復(fù)雜度中證明，那么就更別談在多項(xiàng)式復(fù)雜度中把他的所有條件都證明出來(lái)了。

　　終于可以給出NP問(wèn)題(Non-deterministic Polynomial problem)的完全定義了(沒錯(cuò)，這個(gè)N是不確定的意思)

　　一個(gè)問(wèn)題的一個(gè)解可以用多項(xiàng)式級(jí)復(fù)雜度檢驗(yàn)，它就是NP問(wèn)題

　　所以有一點(diǎn)值得注意的

　　找不到多項(xiàng)式復(fù)雜度解的(非P問(wèn)題)不一定是NP問(wèn)題

　　因?yàn)橛行o(wú)法在多項(xiàng)式復(fù)雜度中檢驗(yàn)一個(gè)解的問(wèn)題存在。

　　同時(shí)，這里可以很明顯的發(fā)現(xiàn)，如果一個(gè)問(wèn)題是P問(wèn)題，那么他肯定能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)檢驗(yàn)任意一組解。于是又可以推出

　　P∈NP

　　但是P=NP嗎？這是一個(gè)世紀(jì)難題，反正了解一下有這個(gè)問(wèn)題就行了，初賽不會(huì)讓你證明的，放心好了。

　　三、NP-hard和NPC問(wèn)題的引入

　　雖然說(shuō)不用讓你去證明P=NP這種鬼畜的東西，但是科學(xué)家不斷嘗試證明的這段歷史是沒準(zhǔn)會(huì)考的。(畢竟這是一種自強(qiáng)不息的求索精神，很符合二十四字核心價(jià)值觀)

　　在此之前我們先引入歸約的定義

　　歸約指的是將A問(wèn)題進(jìn)行歸約后可以用B問(wèn)題的解決方法解決，也就是把A問(wèn)題變成B問(wèn)題解決

　　NPhard問(wèn)題是指

　　如果有一個(gè)問(wèn)題可以使所有NP問(wèn)題在多項(xiàng)式復(fù)雜度內(nèi)歸約到它，那么它就是NP-hard問(wèn)題

　　顯然如果難度有一個(gè)上界的話，解決所有的NP問(wèn)題歸約起來(lái)的問(wèn)題難度肯定就是那個(gè)上界，所以這類問(wèn)題被稱為NP-hard。

　　如果你有了解過(guò)停機(jī)問(wèn)題的話，會(huì)知道這個(gè)問(wèn)題是不可判的，但是如果把問(wèn)題理解成輸入一個(gè)東西到某個(gè)程序里，判斷他是否會(huì)停機(jī)，就可以把所有NP問(wèn)題歸約到停機(jī)問(wèn)題上來(lái)，所以停機(jī)問(wèn)題是NP-hard，于是

　　NP-hard問(wèn)題不一定是NP問(wèn)題

　　既然不一定是NP問(wèn)題那么對(duì)我們解決P=NP就沒啥用了。
所以科學(xué)家又提出了NPC問(wèn)題：

　　一個(gè)NP問(wèn)題可以使所有NP問(wèn)題在多項(xiàng)式復(fù)雜度內(nèi)歸約到它，那么它就是NPC問(wèn)題

　　也就是說(shuō)如果解決了NPC問(wèn)題就可以解決所有的NP問(wèn)題，然后就可以證明P=NP。

　　常見的NPC問(wèn)題有3-SAT問(wèn)題，旅行商問(wèn)題等等。
這些的證明有興趣大家可以研究一下。
最后祭上這張圖來(lái)總結(jié)上面知識(shí)點(diǎn)之間的聯(lián)系

　　接著我們來(lái)切幾道真題。

　　四、歷年真題

　　2012.20．以下關(guān)于計(jì)算復(fù)雜度的說(shuō)法中，正確的有（ ）。
A．如果一個(gè)問(wèn)題不存在多項(xiàng)式時(shí)間的算法，那它一定是NP類問(wèn)題
B．如果一個(gè)問(wèn)題不存在多項(xiàng)式時(shí)間的算法，那它一定不是P類問(wèn)題
C．如果一個(gè)問(wèn)題不存在多項(xiàng)式空間的算法，那它一定是NP類問(wèn)題
D．如果一個(gè)問(wèn)題不存在多項(xiàng)式空間的算法，那它一定不是P類問(wèn)題

　　解析：
A 還記得圖靈停機(jī)問(wèn)題嗎？那是一個(gè)NP-hard而不是NP問(wèn)題
B 這是對(duì)的，因?yàn)镻問(wèn)題的定義是存在多項(xiàng)式時(shí)間的復(fù)雜度算法
C、D 時(shí)間復(fù)雜度和空間復(fù)雜度都是復(fù)雜度，是等價(jià)的。

　　所以選BD

　　2013.14. （ ）屬于 NP 類問(wèn)題。
A. 存在一個(gè) P 類問(wèn)題
B. 任何一個(gè) P 類問(wèn)題
C. 任何一個(gè)不屬于 P 類的問(wèn)題
D. 任何一個(gè)在（輸入規(guī)模的）指數(shù)時(shí)間內(nèi)能夠解決的問(wèn)題

　　解析：
這里考察的知識(shí)點(diǎn)是NP問(wèn)題的定義以及P∈NP
由之前可知任何P問(wèn)題都是NP問(wèn)題，同理一定存在一個(gè)P問(wèn)題是NP問(wèn)題
AB都是對(duì)的
C的話我們可以繼續(xù)用萬(wàn)能的停機(jī)問(wèn)題去反駁他
D考察的是定義，指數(shù)時(shí)間內(nèi)能解決不意味著多項(xiàng)式時(shí)間能驗(yàn)證解，所以D是錯(cuò)的

　　所以選AB

　　那就這樣子了，希望對(duì)大家有所幫助。

　　本文發(fā)布于洛谷日?qǐng)?bào)，特約作者：Styx

　　原文https://www./blog/styx-ferryman/chu-sai-bei-kao-gan-huo-p-wen-ti-np-wen-ti-npc-wen-ti-sha-sha-fen-fou