在講P類問題之前先介紹兩個個概念：多項式，時間復(fù)雜度。(知道這兩概念的可以自動跳過這部分)

1、多項式：axⁿ-bx^n-1+c

恩....就是長這個樣子的，叫x最高次為n的多項式....

咳咳，別嫌我啰嗦。。有些人說不定還真忘了啥是多項式了。。例如第一次看到的鄙人→_→

2、時間復(fù)雜度

我們知道在計算機(jī)算法求解問題當(dāng)中，經(jīng)常用時間復(fù)雜度和空間復(fù)雜度來表示一個算法的運(yùn)行效率。空間復(fù)雜度表示一個算法在計算過程當(dāng)中要占用的內(nèi)存空間大小，這里暫不討論。時間復(fù)雜度則表示這個算法運(yùn)行得到想要的解所需的計算工作量，他探討的是當(dāng)輸入值接近無窮時，算法所需工作量的變化快慢程度。

舉個例子：冒泡排序。

在計算機(jī)當(dāng)中，排序問題是最基礎(chǔ)的，將輸入按照大小或其他規(guī)則排好序，有利于后期運(yùn)用數(shù)據(jù)進(jìn)行其他運(yùn)算。冒泡排序就是其中的一種排序算法。假設(shè)手上現(xiàn)在有n個無序的數(shù)，利用冒泡排序?qū)ζ溥M(jìn)行排序，

①首先比較第1個數(shù)和第2個數(shù)，如果后者>前者，就對調(diào)他們的位置，否則不變

②接著比較第2個數(shù)和第3個數(shù)，如果后者>前者，就對調(diào)他們的位置，否則不變

③一直向下比較直到第n-1和第n個數(shù)比較完，第一輪結(jié)束。（這時候最大的數(shù)移動到了第n個數(shù)的位置）

④重復(fù)前三步，但是只比較到第n-1個數(shù)（將第二大的數(shù)移動到第n-1個數(shù)位置）

⑤持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

舉個實例：5,4,3,2,1，對其進(jìn)行排序，先是比較5跟4變成4,5,3,2,1，第一輪結(jié)束后變成43215，可以計算，當(dāng)對其排序完正好要經(jīng)過4+3+2+1=10次比較，當(dāng)然這是最復(fù)雜的情況，即完全反序。可以知道對于n個數(shù)，至多要經(jīng)過1+2+...+n-1即(n^2-n)/2次比較才能排好序。這個式子里n的最高次階是2，可知道當(dāng)n→∞時，一次性對其比較次數(shù)影響很小，所以我們把這個算法的時間復(fù)雜度比作：o(n^2)。取其最高次，可以看出，這是一個時間復(fù)雜度為多項式的表示方式。

時間復(fù)雜度排序o(1)<o(n)<o(lgn)<o(n^2)<o(n^a)<o(e^n)（a>2,n表示輸入的數(shù)據(jù)個數(shù)，o(1)為常數(shù)級別）

好了，介紹完上面的概念就可以開始講關(guān)于什么叫P類問題了。以上個例子冒泡排序為例，我們知道了，在排序這個大問題里，是可以找到一種時間復(fù)雜度為多項式o(n^2)的算法(如冒泡排序法)來求解排序問題的，所以我們說排序問題是一個有多項式時間算法的問題。

所以我們稱，

P類問題：存在多項式時間算法的問題。(P：polynominal，多項式)

然后扯個題外話，為什么我們要研究這個？因為計算機(jī)處理的輸入常常不是那么幾十個幾千個那么一點(diǎn)點(diǎn)，想象一下，當(dāng)計算機(jī)處理的數(shù)據(jù)達(dá)到100萬個的時候，時間復(fù)雜度為o(n^2)和o(e^n)的算法，所需的運(yùn)行次數(shù)簡直是天壤之別，o(e^n)指數(shù)級的可能運(yùn)行好幾天都沒法完成任務(wù)，所以我們才要研究一個問題是否存在多項式時間算法。而我們也只在乎一個問題是否存在多項式算法，因為一個時間復(fù)雜度比多項式算法還要復(fù)雜的算法研究起來是沒有任何實際意義的。

好了，接下來我們介紹NP，先給定義，

NP類問題：能在多項式時間內(nèi)驗證得出一個正確解的問題。(NP:Nondeterministic polynominal，非確定性多項式)

P類問題是NP問題的子集，因為存在多項式時間解法的問題，總能在多項式時間內(nèi)驗證他。

注意定義，這里是驗證。NP類問題，我用個人的俗話理解就是，不知道這個問題是不是存在多項式時間內(nèi)的算法，所以叫non-deterministic非確定性，但是我們可以在多項式時間內(nèi)驗證并得出這個問題的一個正確解。舉個例子，

著名的NP類問題：旅行家推銷問題(TSP)。即有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的環(huán)路，這個環(huán)路路徑小于a。我們知道這個問題如果單純的用枚舉法來列舉的話會有(n-1)! 種，已經(jīng)不是多項式時間的算法了，(注：階乘算法比多項式的復(fù)雜)。那怎么辦呢？我們可以用猜的，假設(shè)我人品好，猜幾次就猜中了一條小于長度a的路徑，我畫畫畫畫，好的，我得到了一條路徑小于a的環(huán)路，問題解決了，皆大歡喜。可是，我不可能每次都猜的那么準(zhǔn)，也許我要猜完所有種呢？所以我們說，這是一個NP類問題。也就是，我們能在多項式的時間內(nèi)驗證并得出問題的正確解，可是我們卻不知道該問題是否存在一個多項式時間的算法，每次都能解決他(注意，這里是不知道，不是不存在)。

所以這就引出了這類討論的一個千年問題：是否 NP類問題=P類問題？

即，是否所有能在多項式時間內(nèi)驗證得出正確解的問題，都是具有多項式時間算法的問題呢？

太讓人震驚了，要是解決了這個問題，那豈不是所有的NP問題都可以通過計算機(jī)來解決？

圣戰(zhàn)的結(jié)果是，有的存在，有的不存在。=_=

在這場圣戰(zhàn)中，人們還發(fā)現(xiàn)了很多的東東，也就是我們接下來要介紹的NPC問題(啊喂，我不是游戲NPC)和NPH問題。

(PS :網(wǎng)絡(luò)上經(jīng)常有人說，這不是個NP問題嗎，其實很多時候他們說的應(yīng)該是NPC問題，而不是NP問題)

為了證明這個千古難題，科學(xué)家想出了很多辦法。其中之一就是問題的約化。所謂問題約化就是，可以用問題B的算法來解決A ，我們就說問題A可以約化成問題B。舉個例子，一元一次方程的求解，跟二元一次方程的求解，我們知道，只要能求解二元一次方程，那就可以用二元一次方程的解法來求解一元一次方程，只需要將一元一次方程加上y，并附加一個方程y=0就可以將一元一次方程變形為一個二元一次方程，然后用二元一次方程的解法來求解這個方程。注意，這里二元一次方程的解法會比一元一次的復(fù)雜。所以我們說，只需要找到解二元一次方程的規(guī)則性解法，那就能用這個規(guī)則性解法來求解一元一次方程。從這里也可以看出，約化是具有傳遞性的，如A約化到B，B約化到C，A就可以約化到C，同時不斷約化下去，我們會發(fā)現(xiàn)一個很驚人的特性，就是他一定會存在一個最大的問題，而我們只需要解決了這個問題，那其下的所有問題也就解決啦！這就是我們所說的NPC問題的概念?。?！

引到NP問題里就是，對于同一類的所有的NP類問題，若他們都可以在多項式時間內(nèi)約化成最難的一個NP類問題，（我們直觀的認(rèn)為，被約化成的問題應(yīng)具有比前一個問題更復(fù)雜的時間復(fù)雜度）當(dāng)我們針對這個時間復(fù)雜度最高的超級NP問題要是能找到他的多項式時間算法的話，那就等于變向的證明了其下的所有問題都是存在多項式算法的，即NP=P！?。?！給出NPC問題定義。

（3）NPC類問題（Nondeterminism Polynomial complete）：存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。其定義要滿足2個條件： 

首先，它得是一個NP問題；

然后，所有的NP問題都可以約化到它。

要證明npc問題的思路就是： 

先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它。

（4）NP難問題（NP-hard問題）：

    NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC問題的范圍廣，NP-Hard問題沒有限定屬于NP），即所有的NP問題都能約化到它，但是他不一定是一個NP問題。

    NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而更難以解決。

以上四個問題他們之間的關(guān)系可以用下圖來表示：