P、NP、NPC問題詳解

P、NP、NPC

概念

> P問題：能夠在多項式時間内解決的決策問題。

—舉例: 圖搜尋問題、最短路徑問題、最小生成樹問題······

> NP問題：不能在多項式時間内解決或不确定能不能在多項式時間内解決，但能在多項式時間驗證的問題。

—驗證：給定一個問題的執行個體、證書（類似于證據），需要驗證這個證書是這個問題的正确答案。

— 舉例：漢密爾頓路徑，執行個體為G=(V,E)，證書為頂點序列 {v0,v1,v2,v3,….,vk}，我們的目的是要驗證這個證書就是這個問題的答案，驗證方法為：先周遊一遍這個點序列，看看是不是每個點隻出現一次，然後對于(vi,vi+1)是否為G的邊，這樣就能夠驗證這個點序列是不是漢密爾頓路徑，很顯然這個驗證過程是多項式時間的，是以漢密爾頓路徑是NP問題。

> NPC問題：目前不能用多項式時間解決的問題，但是我們還不能證明這個問題不能用多項式時間解決，我們這次的目标是研究這個問題。

—滿足的兩個條件：是一個NP問題 + 所有的NP問題可以在多項式時間内規約到它

—舉例：3SAT、頂點覆寫、團、三維比對、漢密爾頓回路、劃分問題·······

> NP難問題：所有的NP問題可以在多項式時間歸約到它，但它不一定是一個NP問題

> 歸約(約化)的标準概念： 如果能找到這樣一個變化法則，對程式A的任意一個輸入，都能按這個法則變換成程式B的輸入，使這兩個程式的輸出相同，那麼我們說，問題A可歸約為問題B

— 問題A可以約化到問題B的含義是，可以用解決B的解法來解決A，或者說A可以“變成”B。

—A可歸約為B的直覺含義：B的時間複雜度>=A的時間複雜度。也即，A比B簡單。

關系

P、NP、NPC、NP Hard問題的關系如下：

證明NPC問題

證明問題B是NPC問題的過程如下：

1. 證明B是NP問題
2. 知道一個已知的NPC問題A
3. 證明A歸約到B。

常見歸約問題

基本知識

1、獨立集 —— 在圖G = （V，E）中，如果頂點集合S⊆V中的任意兩點之間都沒有邊，則稱S是獨立的。

—難點： 尋找最大獨立集。

—目标： 裝入盡可能多的頂點，要求邊涉及到的邊服從一些限制條件。

2、頂點覆寫 —— 給定圖G = （V，E），頂點集合S⊆V，如果圖中的每一條邊至少有一個端點在S中，則稱S是一個頂點覆寫。

—難點： 尋找最小頂點覆寫。

—目标： 用盡可能少的頂點覆寫圖中的所有邊。

3、集合覆寫 —— 試圖用一組較小的集合覆寫一個任意的對象集合。

常見問題

1、獨立集問題——給定圖G和數k，問是否包含大小至少為k的獨立集？

2、頂點覆寫問題——給定圖G和數k，問G是否包含大小至多為k的頂點覆寫？

3、集合覆寫問題——給定n個元素的集合U，U的子集S1，···，Sm以及數k，問在這些子集中有一組子集，它們的并等于整個U且至多包含k個子集嗎？

4、集合包裝問題——給定n個元素的集合U，U的子集S1，····，Sm以及數k，問在這些子集中至少有k個兩兩不相交嗎？

5、SAT(可滿足性問題)——給定bool變量集X={x1，···，xn}上的一組子句C1，···，Ck，問存在滿足的真值指派嗎？

注意：每個子句均為析取子句(邏輯或∨)，最終結果為各個子句的合取(邏輯與∧)。

6、3-SAT(三元可滿足性問題)——給定bool變量集X={x1，···，xn}上的一組子句C1，···，Ck，每個子句的長為3，問存在滿足的真值指派嗎？

注意：同上。

常用引理

設G=(V, E)是一個圖，S⊆V，那麼S是一個獨立集當且僅當它的補V-S是一個頂點覆寫。

證明：首先，設S是一個獨立集。考慮任一邊e=(u,v)，因為S是獨立集，u和v不可能同時在S中，是以u和v至少有一個在V-S中，即得任一邊至少有一個端點在V-S中，是以V-S是一個頂點覆寫。

反過來，設V-S是一個頂點覆寫，考慮S中的任意兩個頂點u、v，若它們間有一條邊e，那麼e的兩個端點均不在V-S中，這與假設V-S是一個頂點覆寫沖突。是以S中的任意兩點均無連線，是以S是一個獨立集。

歸約的一般思想(要點)：證明Y到X的歸約，要用問題X中的分量構造“零件”來描寫在問題Y中正在做的事

1、 獨立集歸約到頂點覆寫

證明：若有一個解頂點覆寫的黑盒子，那麼通過問黑盒子G是否有大小至多為n-k的頂點覆寫，就能确定G是否有大小至少為k的獨立集。

2、頂點覆寫歸約到獨立集

證明：若有一個可以解獨立集的黑盒子，那麼通過問黑盒子G是否有大小至少為n-k的獨立集，就能确定G是否有大小至多為k的頂點覆寫。

3、頂點覆寫歸約到集合覆寫

證明：若有一個可以解集合覆寫的黑盒子，考慮頂點覆寫的任一執行個體，給定圖G=(V, E)和數k。

構造集合覆寫的一個執行個體，其基集U等于邊E，對圖G的每一個頂點i∈V，設Si⊆U為G中所有和點i相關聯的邊，把Si加入集合覆寫的執行個體中。

U能被集合S1,S2,···,Sn中的至多k個覆寫當且僅當G有大小至多為k的頂點覆寫。于是，給定頂點覆寫的執行個體，如上述的那樣構造集合覆寫的執行個體，并把它輸入黑盒子。回答yes當且僅當黑盒子回答yes。