P問題、NP問題、NPC問題的概念及執行個體證明

美劇《基本演繹法》（也就是美版“福爾摩斯”）第 2 季第 2 集中，兩位研究 NP 問題的數學家被謀殺了，兇手是同行，因為被害者即将證明“P=NP 問題”，她為獨吞成果而下了毒手。然而兇手的動機，并不是千禧年大獎難題那100萬美元的獎金——解決了 P=NP 問題，就能夠破譯世界上所有的密碼系統，這裡面的利益比100萬美元多多了。

劇中隻用了一句話來介紹 P=NP 的意義：“能用電腦快速驗證一個解的問題，也能夠用電腦快速地求出解”。這句過于簡單的話可能讓大家一頭霧水，今天我們就來講一講 P vs. NP。

• • 幾種問題及其關系
  • 規約一種技巧
  • 如何對問題證明
  • NP-Complete間的規約例子
    • • 3SATIndependent Set
      • 3SAT Vertex Cover
      • 3SAT ILP
      • 3SAT Hamiltonian cycle problem
      • Subset sum problem Partition problem
      • Clique problemSubgraph isomorphism problem
      • Partition problem Knapsack problem
      • Vertex Cover Independent Set
      • Independent Set Clique problem
      • Hamiltonian cycle problem Hamiltonian path problem
      • Hamiltonian cycle problem Traveling salesman problem
  • 參考資料

幾種問題及其關系

首先解釋一下什麼是NP問題，什麼是NP hard問題，什麼是NP完全問題。

• P Problem：這個應該最易了解，就是一個問題可以在Polynominal的時間的得到解決，當然，是對于任意input size。
• NP Problem：對于一類問題，我們可能沒有一個已知的快速的方法得到問題的答案，但是如果給我們一個candidate answer，我們能夠在polynominal的時間内驗證這個candidate answer到底是不是我們已知問題的答案，這類問題叫做NP problem。是以很顯然 P Problem是NP problem的一個子集。
• NP-hard Problem：對于這一類問題，用一句話概括他們的特征就是“at least as hard as the hardest problems in NP Problem”， 就是NP-hard問題至少和NP問題一樣難。
• NP-Complete Problem：對于這一類問題，他們滿足兩個性質，一個就是在polynomial時間内可以驗證一個candidate answer是不是真正的解，另一個性質就是我們可以把任何一個NP問題在polynomial的時間内把他的input轉化，使之成為一個NP-complete問題（即規約）。NP-Complete Problem問題可以互相轉換 (在多項式時間内)，隻要其中一個問題可以在多項式時間内解決，那麼其他問題也都将可以在多項式時間内解決。

  

規約——一種技巧

歸約（reduction）： 規約是證明NP-hard問題的一種常用方法，通常用 <= <script type="math/tex" id="MathJax-Element-1"><=</script>這個符号來表示。如 P<=Q ，這個就表示P is reducible to Q , or Q is the reduction from P or P is reduced to Q（P問題可以歸約到Q問題，or可以把P歸約到Q） 。這裡的reduction的符号可以當成是 比較難易程度的小于等于号，意味着P至少比Q容易，或者Q至少比P難。

歸約主要做的就是以下兩個轉化（注意兩個轉化都要在polynomial的時間内完成）【已知 P 是個NP-hard問題，證新問題Q 亦是NP-hard問題】，

1. 把P的輸入轉化到Q的輸入；

2. 把Q的輸出轉化到P的輸出。

下圖展示了上述規約過程。其中 T1 在多項式時間将 P的輸入 Pinput 轉化成Q的輸入 Qinput ; T2 在多項式時間将 Q的輸出 Qoutput 轉化成P的輸出 Poutput 。也就是說NP-hard問題 P 可以依賴于對問題Q 的解決而解決。那麼 Q 至少比P要難，即 P<=Q 。

如何對問題證明

下面來列出了一些常見的證明問題及其證明套路。

• 證明NP問題。這個容易，即給你一個結果，你能在polynomial的時間内驗證該結果的正确性。
• 證明NP-hard問題。我們要證明一個問題是NP-hard的時候，我們通常要做的是找到一個已被證明了的NPC問題，并把這個NPC問題歸約到該問題上去（即NPC<=NP-hard）。
• 證明NP-Complete問題。分以下兩步：
  1. 第一步證明這個問題屬于NP；
  2. 第二步，證明這個問題是NP-hard的。

下圖列出了幾個已被發現NP-Complete問題（更全面的NP-Complete問題清單，見連結A compendium of NP optimization problems，以及List of NP-complete problems），及其規約關系。可以看出所有的NP問題都可以規約到SAT(即NP<=SAT)，也就是說SAT至少與NP問題一樣難，或者如果解決了3SAT問題，所有的NP問題就解決了。同樣的，SAT<=3SAT，3SAT<=Independent Set，Independent Set<=Vertex Cover OR Clique。

規約關系具有傳遞性，是以有3SAT<=Vertex Cover，NP<=NP-Complete。 事實上，由于NP-Complete ⊂ NP 且 NP<=NP-Complete，可以推導出 所有的NP-Complete 可以互相規約，也就是所有的NP-Complete都是等價的。

NP-Complete間的規約例子

1. 3SAT<=Independent Set

• 在圖G中若頂點集合S滿足其中的任意兩個頂點之間不存在邊，則稱S為獨立集。The input of Independent Set is a graph G and a number m（獨立集問題的兩個參數：圖 G 以及獨立集的大小m）, the problem is to find a set of m pairwise non-adjacent vertices(問題是找到G的一個大小為 m 的獨立集).
• 轉化過程：Given an instance 3SAT problem with m clauses, create an instance (G,m) of Independent Set as follows:
  • Graph G has a triangle(edge or vertex) for each clause, with vertices labeled by the clause’s literals
  • Add edge between any two vertices that represent opposite literals.

  • The goal g is set to the number of clauses.

    The graph below corresponding to (x¯∨y∨z¯)∧(x∨y¯∨z)∧(x∨y∨z)∧(x¯∨y¯) (clearly m=3 )

    

  • 假設上圖有一個最大獨立集，則每個三角形中有且僅有一個頂點在該獨立集中，設該頂點取值為1，其餘頂點取值0，則其肯定是一個滿足的3SAT的指派。
• 容易證明該規約過程用了多項式時間。
• 把P的輸入轉化到Q的輸入：P的輸入是包含 m 個clause的3SAT表達式；Q的輸入當然是轉化得到的圖形G以及獨立集的大小參數 g=m 。
• 把Q的輸出轉化到P的輸出：Q的輸出是 G 的一個大小為g的獨立集；P的輸出是3SAT的一個指派。假設 G 中有一個大小為m的獨立集，則一定是1)三角形内部三個頂點隻能取一個 2)不屬于三角形的邊所連接配接的頂點也隻取一個。對于每個clause，如果選擇了 x 對應的頂點，則令x=1，如果選擇了 x¯ 對應的頂點，則令 x¯=1 . 則該指派是滿足的。

2. 3SAT <= Vertex Cover

• 圖的頂點覆寫（有時是節點覆寫）是一組頂點的集合，使得圖的每個邊緣至少與集合中的一個頂點相連接配接。在這裡Vertex Cover問題是給定圖 G 和點集的個數g，要找到圖 G 的一個大小為g的點覆寫。（我們常說的最小頂點覆寫的問題稱為頂點覆寫問題，毫無疑問，它也是一個NP-Complete問題）。
• 轉化過程：
  • 按照如下方法構造Graph，對應每一個變量 xi ，我們構造點二進制點對 xi 和 x¯i ; 對于每一個clause，我們構造三角形的三個頂點，這3個點直接彼此有邊，假設這三個點叫 A,B,C ，我們要建立 A,B,C 這三個點和該clause的聯系：假設我們的clause是 (x1∨x¯2∨x¯3) 我們就把 x1 和 A 連起來，x¯2和 B 連起來，x¯3和 C 連起來。
  • 下面的graph對應于(x1∨x¯2∨x¯3)∧(x1∨x2∨x4)。

    

  • 若上圖存在最小點覆寫，則将二進制點對中在該最小點覆寫中的那一個指派為1。則該指派就是一個滿足3-SAT的指派。
• 假設有 m 個clause，n個變量。則該規約過程建立了 3m+2n 個點， n+3m+3m 個邊。顯然可以在多項式時間完成該轉換。
• 把P的輸入轉化到Q的輸入：P的輸入是包含 m 個clause的3SAT表達式；Q的輸入當然是轉化得到的圖形G以及覆寫集的大小參數 g=2m+n 。
• 把Q的輸出轉化到P的輸出：Q的輸出是 G 的一個大小為g=2m+n的覆寫集；P的輸出是3SAT的一個指派。假設有圖 G 的一個大小為g=2m+n的頂點覆寫，則其中必定包含所有二進制點對中的一個點和三角形的兩個頂點。對于每個clause對應的三角形的三個邊必定被至少一個點覆寫，是以有一個可滿足的真值指派；對于每個二進制點對，如果 xi 在 S 中，則xi=1，如果 x¯i 在 S 中，則xi=0。

3. 3SAT <= ILP

• ILP就是Integer Linear Programming，即所有變量都要求是整數。
• 轉化過程：
  • 對于 每個clause，我們都對應于ILP中的一個constraint，比如 3SAT中有4個變量， x1 ， x2 ， x3 和 x4 ， 則ILP中也有同樣的這4個變量，并且我們要求他們都是隻能取0 或 1。對于一個clause，如 (x1∨x¯2∨x¯3) ，我們對應的constraint是 “ x1+（1−x2）+（1−x3）=1 。很顯然了，ILP中的變量選0對應于3SAT中的變量選 0 ，ILP中的變量選1對應于3SAT中的變量選1.

  • 3SAT問題 (x1∨x¯2∨x¯3)∧(x1∨x2∨x4) 對應的ILP如下：

    {x1+（1−x2）+（1−x3）=1x1+x2+x4=1

• 至于input/output的轉換，就如轉換過程的描述，異常簡單。在此不再叙述。

4. 3SAT <= Hamiltonian cycle problem

• 轉化過程：
  • 對每個變量 xi(1≤i≤n) ，建立 3m+3 個頂點，命名為 vi,1,vi,2,⋯,vi,3m+3 ，并且對相鄰序号的兩個頂點添加互相之間的有向邊。如果 xi=1 ，則形成從左向右的一個路徑；如果 x¯i=1 ，則形成從右向左的一個路徑。
  • 對每個 1≤i≤n−1 ，添加四條有向邊 (vi,1,vi+1,1),(vi,3m+3,vi+1,3m+3),(vi,1,vi+1,3m+3),(vi,3m+3,vi+1,1) 。
  • 添加兩個節點 s,t ，添加有向邊 (s,v1,1),(s,v1,3m+3),(vn,1,t),(vn,3m+3,t) 。然後再添加有向邊 (t,s) 。這時得到的圖中有 hamiltonian cycle，其中一個如下圖的虛線所示。
  • 對于每一個clause cj=z1z2z3 ，建立對應的頂點 cj 。如果 z=xi ，則添加有向邊 (vi,3j,cj)和(cj,vi,3j+1) ; 如果 z=x¯i ，則添加有向邊 (cj,vi,3j)和(vi,3j+1,cj) 。這裡 1≤j≤m,1≤i≤n 。如對子句 c=x1∨x¯2∨x4 生成如下圖中紅色所示。如果選擇子句中 x1=1 ，則 x1 對應的路徑為從左向右；如果選擇 x¯2=1 ，則 x2 對應的路徑為從右到左；如果選擇 x4=1 ，則 x4 對應的 路徑為從左到右。這樣我們就得到了最終的圖 G 。

    

  • 若圖G有Hamiltonian cycle，則對每一個變量 xi 對應的路徑都是單向的，若為從左到右，則 xi=1 ；若為從右到左，則 xi=0 。則該指派肯定是3SAT可滿足的。
• 該轉化過程要建立 (3m+3)n+m+2 個點和 (3m+2)×2×n+4(n−1)+5+2m 個邊，是多項式時間的。
• 把P的輸入轉化到Q的輸入：P的輸入是包含 m 個clause,n個變量的的3SAT表達式；Q的輸入當然是轉化得到的包含 (3m+3)n+m+2 個點和 (3m+2)×2×n+4(n−1)+5+2m 個邊的圖形 G 。
• 把Q的輸出轉化到P的輸出：Q的輸出是G的一個Hamiltonian cycle；P的輸出是3SAT的一個指派。

5. Subset sum problem <= Partition problem

• 問題描述：
  • Subset sum problem：given a set (or multiset) of integers T=(t1,t2,⋯,tn) , is there a non-empty subset whose sum is k 。
  • Partition problem: partition problem (or number partitioning) is the task of deciding whether a given multiset W of positive integers can be partitioned into two subsets W1 and W2 such that the sum of the numbers in W1 equals the sum of the numbers in W2 .
• 轉化過程：

  • 給定一個子集和的執行個體為 T=(t1,t2,⋯,tn) ，數 k 。設∑t∈Tt=A，則在 T 的基礎上添加兩個數{2A−k,A+k}，組成一個劃分問題的執行個體 W ，即W={T,2A−k,A+k}.

    則 ∑w∈Ww=4A 。

  • 假設找到了 W 的一個劃分W1和 W2 ，則有 ∑w∈W1w=∑w∈W2w=2A。

    而且，新添加的兩個元素肯定不會同時在 W1 或 W2 裡，否則二者所在的子集的元素和必定大于二者之和 3A>2A 。 2A−k 所在的子集的其它元素就是一個滿足子集和問題的子集。

• 把P的輸入轉化到Q的輸入：P的輸入是集合 T 以及數k；Q的輸入是 W={T,2A−k,A+k}.
• 把Q的輸出轉化到P的輸出：Q的輸出是 W 的二劃分W1和 W2 ，有 ∑w∈W1w=∑w∈W2w ；P的輸出是 2A−k 所在的子集的其它元素集合。

6. Clique problem<=Subgraph isomorphism problem

• 問題描述
  • Clique problem：給定一個圖 G=(V,E) 和整數 k ，找到G的大小為 k 的團。
  • Subgraph isomorphism problem：給定兩個圖G1=(V1,E1),G2=(V2,E2)，能否找到 G1 的一個子圖 H ，使得H與 G2 同構。
• 轉換過程：
  • 令 G1=G ，構造 G2 為包含 k 個頂點的完全圖（即團）。
  • 如果子圖同構問題的答案是肯定的，那麼枚舉G中的任意 k 個頂點并判定其是否是團，複雜度是多項式的Ckn。
• 把P的輸入轉化到Q的輸入：P的輸入是圖 G=(V,E) 和整數 k ；Q的輸入是G1和 G2 。
• 把Q的輸出轉化到P的輸出：Q的輸出是Yes/No；P的輸出是 G 的一個團。

7. Partition problem <= Knapsack problem

• 問題描述：
  • Partition problem： partition problem (or number partitioning) is the task of deciding whether a given multiset W of positive integers can be partitioned into two subsets W1 and W2 such that the sum of the numbers in W1 equals the sum of the numbers in W2 , i.e. ∑t∈W1t=∑t∈W2t=∑t∈Wt2.
  • Knapsack problem：Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. 給定一個物品集合 U={u1,u2,⋯,un} ，且每個物品有大小 s(u) 和價值 w(u) ，正整數 B 和正數K，是否存在子集 U′⊂U 使得 ∑u∈U′s(u)≤B,∑u∈U′w(u)≥K.
  • 轉化過程：

    • For each t∈W ，構造一個item u 且s(u)=w(u)=t, 然後對 B,K 添加如下條件 B=K=∑u∈Uu2，

      那麼有 ∑u∈U′s(u)=∑u∈U′w(u)=∑u∈Uu2。

  • 8. Vertex Cover <=Independent Set

    • 問題描述：
      • Vertex Cover：給定一個圖 G=(V,E) 和整數 k ，找到G的大小為 k 的點覆寫。
      • Independent Set：給定一個圖G=(V,E)和整數 k ， 找到G的大小為 k 的獨立集。
    • 轉化過程：
      • 把參數為G=(V,E)和整數 k 的點覆寫問題轉化為參數為G=(V,E)和整數 |V|−k 的獨立集問題。
      • 若 G 中有|V|−k大小的獨立集 S′ ，則 G 中的任意一條邊的兩端點不可能都在S′裡。也就是說， G 的任意一條邊至少與該獨立集S′之外的其餘 k 個頂點的某一個關聯，即該獨立集S′之外的其餘 k 個頂點是G的一個大小為 k 的點覆寫。
    • 把P的輸入轉化到Q的輸入：P的輸入是圖G=(V,E)和整數 k ；Q的輸入是圖G=(V,E)和整數 |V|−k ；
    • 把Q的輸出轉化到P的輸出：Q的輸出是 G 的|V|−k大小的獨立集 S′ ，P的輸出是 V−S′ .

    9. Independent Set <= Clique problem

    • 問題描述：
      • Independent Set：給定一個圖 G=(V,E) 和整數 k ， 找到G的大小為 k 的獨立集。
      • Clique problem：給定一個圖G=(V,E)和整數 k ，找到G的大小為 k 的團。
    • 轉化過程：
      • 把G的大小為 k 的獨立集問題轉化為補圖G¯的大小為 k 的團問題。
      • 如果找到補圖G¯的大小為 k 的團，則該團内的任意兩個頂點在原圖G中沒有連接配接邊，即該團的 k 個頂點是原圖G的大小為 k 的獨立集。
    • 把P的輸入轉化到Q的輸入：P的輸入是圖G=(V,E)和整數 k ；Q的輸入是補圖G¯和整數 k ；
    • 把Q的輸出轉化到P的輸出：Q的輸出是補圖G¯的 k 大小的獨立集S′，P的輸出是 V−S′ .

    10. Hamiltonian cycle problem <= Hamiltonian path problem

    • 問題描述：
      • Hamiltonian cycle problem：a graph cycle (i.e., closed loop) through a graph that visits each node exactly once
      • Hamiltonian path problem： a graph path between two vertices of a graph that visits each vertex exactly once.
    • 轉化過程：

      

      • 在原圖 G 基礎上再添加s,w,t三個頂點，任選 G 中一點u，連接配接 (s,u),(w,t) 以及連接配接 u 的所有相鄰節點與w，生成新圖 G′ 。如上圖所示。
      • 假設新圖 G′ 有一個Hamiltonian path <s,u,v1,v2,⋯,v,w,t> <script type="math/tex" id="MathJax-Element-270"> </script>，由于 u,v 為相鄰節點，故 <u,v1,v2,⋯,v> <script type="math/tex" id="MathJax-Element-272"> </script>為 G 的Hamiltonian cycle。

    11. Hamiltonian cycle problem <= Traveling salesman problem

    • 問題描述：
      • Hamiltonian cycle problem：a graph cycle (i.e., closed loop) through a graph G=(V,E) that visits each node exactly once。
      • Traveling salesman problem： 即給定一個帶權圖 G′=(V′,E′) 和數 k ，找到一個費用為k的回路。
    • 轉化過程：如何得到 G′=(V′,E′) 和數 k
      • V’=V，k=0..
      • E’為完全圖的邊。還要定義邊的權重：w(u,v)={0,if(u,v)∈E1,if(u,v)∉E
      • 如果 G′=(V′,E′) 有個費用為 k=0 的回路，則說明這些邊都是在 G 中存在的，是以是G的一個Hamiltonian cycle problem。

    參考資料

    • 關于P，NP，NPC等問題
      • http://blog.csdn.net/wwy851/article/details/6082007
      • http://blog.csdn.net/wwy851/article/details/6082025

    • 澄清P問題、NP問題、NPC問題的概念

      http://www.matrix67.com/blog/archives/105

    • 完備 (複雜度)

      http://zh.wikipedia.org/wiki/%E5%AE%8C%E5%82%99_(%E8%A4%87%E9%9B%9C%E5%BA%A6)

    • P/NP/NPC/NP-hard

      http://ccckmit.github.io/ct/htm/book.html

    • Cook-Levin理論

      http://zh.wikipedia.org/wiki/Cook-Levin%E7%90%86%E8%AB%96

      提到了兩篇論文

    • A Sample Proof of NP-Completeness

      http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2001/CW/npproof.html

    • 算法導論自學筆記

      http://blog.csdn.net/xiazdong/article/category/1270511

    • Reductions & NP-completeness

      https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/npcomplete.pdf

    • Reductions Between NPCs

      http://mlnotes.com/2013/04/29/npc.html

    • Lecture Notes on Complexity and NP-completeness 1. Reduc

      http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/npc.pdf

    • Reductions Between NPCs

      http://mlnotes.com/2013/04/29/npc.html

    • Everyday encounters with NP-complete problems

      http://cstheory.stackexchange.com/questions/446/everyday-encounters-with-np-complete-problems

    • NP-hardness of an optimization problem

      http://cstheory.stackexchange.com/questions/14787/np-hardness-of-an-optimization-problem?rq=1

    • Is the following optimization problem NP-hard?

      http://cstheory.stackexchange.com/questions/10615/is-the-following-optimization-problem-np-hard

    • Is the following optimization problem (a variant to a previous problem) NP-hard?

      http://cstheory.stackexchange.com/questions/10727/is-the-following-optimization-problem-a-variant-to-a-previous-problem-np-hard?rq=1

    • What are NP-complete problems and why are they so important?

      http://math.stackexchange.com/questions/726/what-are-np-complete-problems-and-why-are-they-so-important