在以往的算法中，所接觸到的大都是多項式時間內(nèi)可完成的算法，比如O(n),O(nlogn),O(n^2)…，但仍存在一些算法的時間復(fù)雜度為：O(n^logn),O(2^n),O(n!)是非多項式時間算法，當(dāng)此類程序規(guī)模一旦過大，便成為目前的計算機解決不了的難題。因此嘗試用NP完全理論進行理解。

目錄

NP問題—基本概念、規(guī)約

基本概念：P問題

基本概念：NP問題

基本概念：NPC問題

基本概念：P、NP、NPC問題的關(guān)系

基本概念：判斷一個問題是否為NP問題

基本概念：歸約性

準(zhǔn)確定義（歸約）

規(guī)約特點

基本概念：歸約證明

NP問題—P問題的證明?

2合取范式（CNF）的可滿足性問題（SAT）

2合取范式（CNF）到圖的轉(zhuǎn)換

NP問題—NPC問題的證明?

第一個NPC問題

公式可滿足性證明

3CNF問題

團問題

證明NP問題

3CNF可以規(guī)約為團問題

證明其實例對應(yīng)性與輸出一致性

頂點覆蓋

首先證明實例對應(yīng)性?

接著證明輸出一致性

NP問題—基本概念、規(guī)約

基本概念：P問題

定義P類問題（polynominal）：在多項式時間內(nèi)可以解決的問題。

P類問題通常被認(rèn)為是比較容易解決的問題，它的時間復(fù)雜度通常為多項式時間，如O(n)，O(nlogn)，O()等等。數(shù)據(jù)結(jié)構(gòu)與算法中學(xué)習(xí)的搜索、排序、小數(shù)背包問題等都是P類問題。

基本概念：NP問題

定義NP類問題（Nondeterministic Polynominal）：給定一個證書（certificate）也可以理解為一個解或結(jié)果，可以在多項式時間內(nèi)驗證此證書是否是問題的一個解的問題。比如，在哈密頓回路中，我們給出一個所有節(jié)點的序列，即證書，可以很容易在多項式時間內(nèi)驗證這個證書是否是一個哈密頓回路。?

簡單來說，一個問題是P問題，則其也一定是NP問題，反之一個問題是NP問題，則并不一定是P問題。一個問題是NP問題要證明其一定是P問題，也就P=NP，這還屬于一個未解難題，因此通常認(rèn)為P≠NP。

基本概念：NPC問題

定義NPC問題（NP完全問題）是NP類問題中最難的問題，包含兩個條件：

1. 1.是一個NP問題（其實是首先限定了一個問題的難度范圍，不能太難，至少可驗證解）
2. 2.所有的NP問題都可以‘轉(zhuǎn)換’成此問題（確切的定義是：所有的NP問題都可以歸約（reducibility）成此問題，此處為了方便理解，用‘轉(zhuǎn)換’來代替）

補充：也有一類問題叫NP Hard問題，相較于NPC問題，它沒有要求一個NP問題這個條件，也就是意味著其甚至在多項時間解都不可驗證。

基本概念：P、NP、NPC問題的關(guān)系

目前普遍認(rèn)為P≠NP，雖然還沒有得到確切證明。

基本概念：判斷一個問題是否為NP問題

• >也就是給出一個證書（解），可否在多項式時間內(nèi)判斷它是否為原問題的一個解
• >最優(yōu)化問題需要轉(zhuǎn)化為判斷性問題

比如給一你一個數(shù)組排序結(jié)果，判斷其是否降序排列，很容易驗證。而如果是著名的旅行商問題，也就是在在一個完全圖中，找到一個最短回路?，F(xiàn)在給你一個完全圖，和一個回路，可以驗證其是否為回路，但卻很難驗證是否為最短回路，也就是旅行商問題的一個解。旅行商問題便是最優(yōu)化問題，那么可以考慮轉(zhuǎn)化：

旅行商問題轉(zhuǎn)化為：

• >此圖中是否存在總權(quán)重為1的回路？
• >此圖中是否存在總權(quán)重為2的回路？
• …
• >此圖中是否存在總權(quán)重為n的回路？

轉(zhuǎn)化為這樣的問題，便可以從第一個問題開始判斷，直到判斷出已存在的權(quán)重最小的回路，便是旅行商問題的最優(yōu)解。同理，一個優(yōu)化問題可分解為多個判定性問題如果能夠證明一個判定性問題為NP難時，顯然原問題也是NP難的

基本概念：歸約性

通俗的講，一個問題（如Q1）可以規(guī)約為另外一個問題（如Q2）是指問題Q1可以轉(zhuǎn)換為問題Q2，之后可以通過求解Q2的方法來求解Q1

如：求解一元一次方程（問題Q1）可歸為求解一元二次方程（問題Q2）：一元二次方程的二次項系數(shù)為0即可，之后可以通過求解一元二次方程的方法來求解一元一次方程

準(zhǔn)確定義（歸約）

一個問題（Q1）可以規(guī)約為另外一個問題（Q2），需滿足以下兩個條件：

1. 1.實例對應(yīng)性：Q1的任意一個實例Ф，通過函數(shù)f都可轉(zhuǎn)化成Q2的一個實例f(Ф)，且這個轉(zhuǎn)化函數(shù)f(Ф)必須為多項式時間；
2. 2.輸出一致性：規(guī)約后的輸出和原來的輸出一致，即，如algo1是Q1的算法，algo2是Q2的算法，則在相同的輸入下，algo1（Q1）=algo2（Q2）。

規(guī)約特點

• 1.歸約具有傳遞性
• 2.如果問題A可歸約為問題B，問題B可歸約為問題C，則問題A一定可歸約為問題C。

基本概念：歸約證明

怎么去證明一個問題轉(zhuǎn)換到另一個問題，這是一種規(guī)約呢？可按如下幾點，分別證明實例的對應(yīng)性和輸出的一致性。

• ? ? 1.Q1問題的任意一個實例都可以轉(zhuǎn)化為Q2問題的一個實例。
• ? ? 2.這個轉(zhuǎn)化過程是多項式時間內(nèi)可以完成的，或者說轉(zhuǎn)化函數(shù)f是個多項式函數(shù)。
• ? ? 3.Q1問題的任意一個實例，如果其輸出為真，則對應(yīng)Q2問題實例的輸出也一定為真。
• ? ? 4.Q2問題的任意一個實例，如果其輸出為真，則對應(yīng)Q1問題實例的輸出也一定為真

如果問題Q1可以歸約為問題Q2，則記為Q1Q2，表示Q1小于Q2的難度不會超過一個多項式時間因子（但通常我們可以根據(jù)小于等于號≤來通俗的認(rèn)為Q1的難度要小于等于Q2）。Q1Q2，可以推出：

• 如果Q1是NPC問題，則Q2必然是NPC問題（因Q2不比Q1容易）；
• 如果Q2是P問題，則Q1必然是P問題（因Q1不比Q2難）；

其實很容易理解，NPC問題代表是較難的問題，Q1都屬于NPC，那么比Q1還難的Q2自然也是NPC問題；P問題代表是簡單的問題，如果Q2屬于P問題，那比Q2還簡單的Q1自然也是P問題。

NP問題—P問題的證明?

根據(jù)概念，已知能夠設(shè)計一個算法，在多項式時間內(nèi)解決一個問題，那這個問題就是屬于P問題。而如果目前的問題找不到這樣一個算法去直接解答，就需要采用證明的方式去驗證其是P問題。即如果一個問題Q1能夠規(guī)約到Q2，且已知Q2是P問題，那么Q1也必然是P問題。

2合取范式（CNF）的可滿足性問題（SAT）

定義（2CNF-SAT）2CNF是一個布爾表達(dá)式，其由子句（clause）的‘與’組成，而每個子句都由2個文字（literal，文字為一個變量或者變量的‘否’）的‘或’組成。如

，

其中共有x，y，z三個變量，這些變量及其’否’為文字，兩個文字構(gòu)成了一個子句。2CNF的可滿足性問題是指是否存在一個賦值，使得2CNF為真。

2合取范式（CNF）到圖的轉(zhuǎn)換

設(shè)2CNF-SAT有n個變量，m個子句，構(gòu)造圖G=(V,E)，圖中共2n個節(jié)點，代表n個變量及每個變量的‘否’。對于2CNF中的每個子句，如，則圖中同時存在從節(jié)點到節(jié)點y的有向邊，和從到x的有向邊。?

如下圖，3個變量對應(yīng)圖中有6個節(jié)點，4個子句對應(yīng)圖中有8條邊，當(dāng)且僅當(dāng)2CNF中存在子句，圖G中存在邊和邊

也就可順勢推出結(jié)論

1. 如圖G中存在邊，則必然會同時存在邊。
2. 如圖中包含一條x到y(tǒng)的路徑，則必然也包含一條從到的路徑。

定理：2CNF是不可滿足的，當(dāng)且僅當(dāng)存在變量x，使得在圖G中同時存在

• 一條x到?x的路徑
• 一條?x到x的路徑

可用反證法來證明以上定理，也就是2CNF是可滿足的，且同時又存在上面兩條路徑。(具體證明有需要可以之后補上)。這就將2CNF的可滿足性問題()轉(zhuǎn)換到圖中是否存在x→?x和?x→x的路徑的問題()，這也是一個規(guī)約的過程，

?要證明以上這個規(guī)約的結(jié)論，就看其是否滿足上面提到的證明規(guī)約的4個點：

• 1.實例的對應(yīng)性：構(gòu)造圖的實例就是按照2CNF問題的實例來轉(zhuǎn)的；并且是頂點和邊的數(shù)量是對應(yīng)的變量和子句的2倍，也是在多項式時間內(nèi)可完成的轉(zhuǎn)化。
• 2.輸出的一致性：由以上定理證明了一組2CNF的賦值會固定對應(yīng)圖中存在的路徑情況；而對于圖問題中的實例的路徑，也會對應(yīng)到2CNF的值為真或假。

已證明這是個規(guī)約過程，接下來要試圖驗證推理：

在以上方法得出的圖G=(V,E)中，可以在多項式時間內(nèi)驗證是否同時存在x→?x和?x→x路徑，也就是問題是P問題。

這其實很簡單，只需要對于圖G中的任意節(jié)點，通過廣度優(yōu)先（或者深度優(yōu)先）算法(復(fù)雜度為O(m))得出到其他節(jié)點的路徑，遍歷所有的節(jié)點就可以驗證圖G是否同時存在x→?x和?x→x的路徑。復(fù)雜度為O(mn)，所以問題是P問題。再結(jié)合之前的結(jié)合定理和推論，得出2CNF可滿足性問題是P問題。

NP問題—NPC問題的證明?

這是最重要的一部分，其實也與上面類似，就是規(guī)約問題的證明。

回顧NPC問題的定義為：

• 此問題是一個NP問題
• 所有的NP問題都可以歸約為此問題

第一點還比較容易，第二點就比較復(fù)雜，但可以利用規(guī)約的傳遞性，所有的問題NP都能歸約到一個已知的NPC問題，也就能歸約到要求的問題Q，所以需證：

1. 問題Q是一個NP問題
2. 一個已知的NPC可以歸約為問題Q

第一個NPC問題

所以需要找第一個NPC問題，才能讓越來越多的NP問題進行規(guī)約。便是電路可滿足性問題：

• 電路可滿足性問題問題：給定一個邏輯電路，問是否存在一種輸入使輸出為True
• 其它的NPC問題都是由這個問題歸約而來的。因此，邏輯電路問題是NPC類問題的“鼻祖”
• 有了第一個NPC問題后，一大堆NPC問題就出現(xiàn)了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題歸約到它就行了

電路的可滿足問題簡單來說也就是給你一個電路，試問存不存在一組輸入，使得電路的輸出為真

有了第一個NPC問題，再來證明公式的可滿足性問題，比如給了一個公式，試問存不存在一種賦值使其為真。也可以看出判斷一個問題是不是NPC問題，全部都是判斷真假的驗證性問題。

所以第一個需要證的是：這是一個NP問題，

首先證明SAT∈NP，為此我們只要證明SAT的任意實例Ф，Ф的可滿足指派組成的證書（解）可以在多項式時間內(nèi)驗證，驗證算法：

• 將公式Ф中的每個變量用相應(yīng)的值代換；
• 計算所得的表達(dá)式。如果表達(dá)式的值是1，則公式Ф可滿足。

顯然上述的驗證算法的復(fù)雜度是關(guān)于n+m的多項式，即O(n+m)。

接下來需要證：這是一個NPC問題，就需要從電路歸約到公式可滿足性。顯而易見的是每個邏輯電路都可以寫成一個布爾公式。

• 也就是存在f，使得任何一個實例x屬于電路，當(dāng)且僅當(dāng)f(x)屬于公式
• 但如果直接這么寫，因每個電路門輸出線扇出為2或者2以上導(dǎo)致布爾公式的規(guī)模出現(xiàn)指數(shù)增長

每個電路輸出線扇出≥2的話，就很像數(shù)據(jù)結(jié)構(gòu)中的滿二叉樹或者多叉樹，節(jié)點數(shù)是呈指數(shù)型增長的，因此不能按這樣的方法來構(gòu)造。但我們并不需要完全的等價，只需要滿足輸出一致性就可以。

公式可滿足性證明

實例對應(yīng)性：
我們的目的不是將電路轉(zhuǎn)換為布爾公式，而是證明可滿足性，如果電路有可滿足指派，則電路每個門輸出都由其輸入決定，寫成表達(dá)式如，這樣轉(zhuǎn)換的話，邏輯電路和布爾表達(dá)式的輸出就是一致的。這就證明了實例對應(yīng)性。

輸出一致性：

• 以上轉(zhuǎn)換為多項式時間
• 如果電路有可滿足性實例，則電路輸出為1，而公式輸出也為1
• 如果公式輸出為1，則顯然邏輯電路輸出也為1

3CNF問題

之前證明了2CNF是個P問題，現(xiàn)在來證3CNF形如下面公式的可滿足性是NPC問題：?

需要證明：?

• 這是一個NP問題
• 公式可滿足性可以歸約到3-CNF（已經(jīng)證明了公式可滿足性是NPC）

需要做的是：

1. 將布爾公式轉(zhuǎn)換為子句的合取式
2. 將子句轉(zhuǎn)換為合取范式
3. 將子句轉(zhuǎn)為3個文字的合取取式

第一步就是建立語法樹，把給定的布爾公式的語法樹畫下來，如下圖。

?再將語法樹看作邏輯電路，由上面可知，邏輯電路可以轉(zhuǎn)換為合取范式

在轉(zhuǎn)換為合取范式，對上圖中的每個子句建立一個真值表，將真值表中為0的項，得到析取范式

?得到的析取范式等價于子句的否，運用德摩根定律，得出合取子句（將析取范式再取否）

而有時我們并不一定能得到如此恰好的每個子句中都有3個文字的情況，比如可能有2個文字，這時候可以隨便合取一個變量p或?p，只是為了滿足每個字句必須恰有3各不同的文字的語法要求

?以上的映射都是多項式時間，

• step1：將布爾公式轉(zhuǎn)換為子句的合取式
• ·同布爾電路轉(zhuǎn)換為布爾公式
• step2：將子句轉(zhuǎn)換為合取范式
• ·每個子句至多變?yōu)?個子句（至多3個變量）
• step3：將子句轉(zhuǎn)為3個文字的合取取式
• ·至多引入4個子句

整個過程的轉(zhuǎn)變基本都是等價的，所以對布爾公式和3CNF的賦值都會得到固定的真或假，所以這就是一個規(guī)約的過程。布爾公式是NPC問題，3CNF就也是NPC問題。

團問題

無向圖G=(V,E)中的團（clique）是一個頂點子集V'V，其中每一對頂點之間都由E中的一條邊來連接。換句話說，一個團是G的一個完全子圖。團的規(guī)模是指它所包含的頂點數(shù)。團問題是關(guān)于尋找圖中規(guī)模最大的團的最優(yōu)化問題。作為判定問題，我們僅僅要考慮的是：在圖中是否存在一個給定規(guī)模為k的團？其形式定義為：

CLIQUE={<G,k>:G是一個包含規(guī)模為k的團的圖}

那么團問題這樣的最優(yōu)化問題，要轉(zhuǎn)換為判斷型問題，也要證明其是個NPC問題

證明NP問題

首先證明其是一個NP問題，這相對來說還比較容易，也就是給一個解（證書）對于一個給定的圖G來說，通過檢查它的邊是不是屬于圖的邊集，就可以在多項式的時間內(nèi)確定其是否為團

3CNF可以規(guī)約為團問題

想要構(gòu)造圖可通過

• 一個子句對應(yīng)一組頂點
• 對于在意兩個在不同組的頂點，如果滿足“這兩個頂點不是‘否’的關(guān)系”這一條件，就用一條邊連接

如下圖可觀察到，左邊三個點是第一個子句，中間三個點是第二個子句，右邊三個點是第三個子句，而一組頂點之間都不存在邊，跟其他組的任意一個頂點，只要不是否的關(guān)系則都有邊連接。

證明其實例對應(yīng)性與輸出一致性

子句數(shù)量m對應(yīng)頂點的個數(shù)是3m，一共3m個頂點，最多3m(m-3)條邊，因此這是可以在多項式時間內(nèi)轉(zhuǎn)換的。如果存在一組賦值使得子句為1，所以必然存在一個規(guī)模為m的團，那么m個子句都為1，其中必定存在一個文字值為1，比如值為1，則在3個變量中必定存在一個值為1的，因此圖中必定存在一個團且規(guī)模為m；相反如果存在規(guī)模為m的團，也就是說三個組的節(jié)點，必然有一個有一個節(jié)點屬于這個團，節(jié)點對應(yīng)的文字為真，整個表達(dá)式就是真。

上面是一個特殊的圖，能說明一般圖的團也是NPC問題嗎？答案是可以的，普通包含特殊，如果說普通的團是P問題，那么特殊的團自然也是P問題。而團在這種受限的情況下才是NPC，那么在一般的圖中必然也是NPC問題。

頂點覆蓋

給定一個IVI個點和|E|條邊的無向圖G(V,E)，找出最小數(shù)目的頂點集合S，使得G中的每條邊都至少被集合S中的一個頂點覆蓋，這就是頂點覆蓋問題。如下圖所示，點集合{b,e,f}是一個頂點覆蓋，頂點覆蓋中點的數(shù)目k=3，顯然，頂點覆蓋不是唯一的，如圖中{b,d,c}也是頂點覆蓋，但頂點覆蓋點的數(shù)目k是唯一的。

頂點覆蓋問題一般要求我們找能覆蓋所有邊最少的頂點集，這是一個最優(yōu)化問題，那便可以轉(zhuǎn)化為一個判斷型問題，也就是問圖中是否存在一個數(shù)目為m的頂點覆蓋集。

現(xiàn)在要證明其是否為一個NPC問題，仍按照步驟：

首先證明其是個NP問題，即給定一個點集，問其是否為某張圖的規(guī)模為k的頂點覆蓋集，只需要帶到圖中進行驗證即可。那么要用什么問題來規(guī)約頂點覆蓋問題？便需要引入補圖和團，團問題可以規(guī)約為頂點覆蓋問題。

補圖便是與一個已有的圖對應(yīng)的有相同的節(jié)點集V，但原圖中有的邊補圖中沒有，原圖中不存在的邊補圖中便有，那么一個圖中的最大團在補圖中便成了一個最大的獨立集S，其包含所有節(jié)點之間都不存在邊，那么圖中不包含在S內(nèi)的節(jié)點V-S便包含了圖中所有的邊，這恰巧符合了頂點覆蓋集的定義，所以其便是一個頂點覆蓋集。

按照思路，為了證明頂點覆蓋問題，需要定義原圖G(V,E)的補圖G(V,E)，如下圖所示，圖(b)為圖(a)的補圖。

首先證明實例對應(yīng)性?

1. 團問題的任意一個實例可以轉(zhuǎn)化為頂點覆蓋問題的一個實例團問題的一個實例為一張無向圖，其可以映射一張補圖，為頂點覆蓋的一個實例，得證。
2. 團問題實例到頂點覆蓋問題實例的轉(zhuǎn)換是一個多項式時間補圖的頂點數(shù)和原圖的頂點數(shù)是一樣的，而補圖的邊是原圖的邊的補集，顯然這個轉(zhuǎn)化是多項式時間?

接著證明輸出一致性

1. 如果G(V,E)的團為S，其規(guī)模為k，則G'的頂點覆蓋為(V-S)，其規(guī)模為|V|一k
2. 如果G'(V,E')的頂點覆蓋為S'，其規(guī)模為|V|-k，則G的團為(V-S')，其規(guī)模為k

第一個也就是證明如果原圖G存在大小為S的團，那么補圖G'必定存在V-S的頂點覆蓋集(V為圖的所有點集)。也就是要證明在G'中一條邊的兩個頂點e1，e2，至少有一個是∈V-S；相當(dāng)于要證在G'中至少有一個不∈S。對應(yīng)在原圖G中，e1和e2之間不存在邊，那邊可知至少有一個節(jié)點不∈S（如果都屬于S則原圖便存在邊了）便可以推回去證明了。

而第二個問題，也就是要整(V-S')中的任意兩節(jié)點在原圖G中都有邊，如果這兩個點都不屬于S'，那么在G'中必定是沒有邊，在G中便一定有邊。因此得證第二點。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-763575.html

?

到了這里，關(guān)于一文理解NP完全理論，NP問題，NPC問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！