P\\NP\\NPC問題

 PNPNPC問題   
    
  1。基本概念：問題複雜度和算法複雜度；具體問題和抽象問題；判定性問題；  
   
  2。編碼對問題解決效率的影響（效率與編碼方式的依賴性相當嚴重），多項式相關編碼，多項式時間可計算函數；  
   
  3。複雜類P  
  A   polynomially   bounded   algorithm   is   one   with   its   worst-case   complexity   bounded   by   a   polynonial   function   of   the   input   size.  
  A   polynonially   bounded   problem   is   one   for   which   there   is   a   polynomially   bounded   algorithm.  
  The   class   P   is   the   class   of   decision   problems   that   are   polynomially   bounded  
   
  定義一：多項式時間內可解決的具體判定性問題的集合；  
  定理一：設Q是定義在實例集I上的一個抽象判定問題，e1,e2是I上的多項式相關編碼，則e1(Q)∈P   ←→   e2(Q)∈P  
   
  定義二：P   =   {L包含於{0,1}*   |   存在一個算法A可在多項式時間內判定L   }  
  定理二：P   =   {L包含於{0,1}*   |   存在一個算法A可在多項式時間內接受L   }，定理二的證明采用模擬論證；  
   
  定義三：P是確定型單帶圖靈機在多項式時間內可判定的語言類：   P=∪TIME(n^k),   k   =   0,1,2...  
  其中時間複雜類TIME(t(n))定義為   TIME(t(n))={L   |   L是一個由O(t(n))時間的圖靈機判定的語言}  
   
  4。多項式時間驗證：  
  有一個算法A所驗證的語言是：   L={x∈{0,1}*   |   存在y∈{0,1}*滿足A(x,y)=1}  
   
  5。複雜類NP：  
   
  定義一：一個語言L屬於NP當且僅當存在一個兩輸入的多項式時間算法A和常數c滿足：  
  L={x∈{0,1}*   |   存在一個證書y,   |y|=O(|x|^c),   滿足A(x,y)=1   }  
  即算法A在多項式時間內驗證了語言L。  
   
  定義二：一個語言在NP中，當且僅當它能被某個非確定型多項式時間圖靈機判定，即   NP=∪NTIME(n^k),   k   =   0,1,2...  
  其中時間複雜類NTIME(t(n))定義為   NTIME(t(n))={L   |   L是一個被O(t(n))時間的非確定型圖靈機判定的語言}  
   
  A   polynomial   bounded   nondeterministic   algorithm   is   one   for   which   there   is   a   (fixed)   polynomial   function   p   such   that   for   each   input   of   size   n   for   which   the   answer   is   yes   ,   there   is   some   execution   of   the   algorithm   that   produces   a   yes   output   in   at   most   p(n)   steps.  
  The   class   NP     is   the   class   of   decision   problems   for   which   there   is   a   polynonial   bounded   nondeterministic   algorithm.  
  解釋說明：nondeterministic   algorithm就是定義一中的那個驗證算法A，  
  nondeterministic   algorithm會用某種非確定性的算法生成一個證書並對其進行驗證，然後輸出結果；  
  上述的英文定義實際上是從非確定性多項式時間圖靈機的角度來定義NP類，即和定義二等價；  
   
  注意：   L∈P   →   L∈NP，   因此P包含於NP；目前還不知道P是否等於NP  
   
  證明一個問題L屬於NP，隻要證明對於L的一個輸入實例x和該實例的一個證書y(y的編碼長度是輸入x的編碼長度的多項式)，存在一個多項式時間的算法A可以驗證y是否滿足x  
   
  6。P在交並補和Kleene*運算下封閉（證明）；NP在交並補和Kleene*運算下是否封閉還未知；  
   
  7。多項式時間化簡：  
  如果存在一個多項式時間的可計算函數f:{0,1}*   →   {0,1}*，滿足對於所有的x∈{0,1}*，   x∈L1   ←→   f(x)∈L2，    
  則稱L1在多項式時間內可化簡為L2,記作L1   <=p   L2  
   
  Polynomial   Reduction  
  Let   T   be   a   function   from   the   input   set   for   a   dicision   problem   P   into   the   input   set   for   Q.   T   is   a   polynomial   reduction   from   P   to   Q   if:  
  T   can   be   computed   in   polynomial   bounded   time  
  x   is   a   yes   input   for   P   →   T(x)   is   a   yes   input   for   Q  
  x   is   a   no   input   for   P   →   T(x)   is   a   no   input   for   Q  
   
  polynomially   reducible    
  Problem   P   is   polynomially   reducible   to   Q   if   there   exists   a   polynomial   reduction   from   P   to   Q,   denoted   as:   P   <=p   Q  
   
  8。定理：如果L1,L2包含於{0,1}*，滿足L1   <=p   L2，則L2∈P   →   L1∈P    
   
  該定理用構造法易證；這個定理可用於證明某個問題是否為NP；  
   
  If   P   <=p   Q   and   Q   is   in   P,   then   P   is   in   P  
  The   complexity   of   P   is   the   sum   of   T,   with   the   input   size   n,   and   Q,   with   the   input   size   p(n),   where   p   is   the   polynomial   bound   on   T,    
  So,   the   total   cost   is:   p(n)+q(p(n)),   where   q   is   the   polynomial   bound   on   Q.  
  (If   P   <=p   Q,   then   Q   is   at   least   as   “hard”   to   solve   as   P)  
   
  和這個定理相關的一個引理：  
  對多項式時間的子程序間進行至多常數次調用的算法的運行時間還是多項式時間；  
  但是對多項式時間的子程序間進行多項式次調用可能產生一個指數時間的算法；  
   
  該引理表明了多項式時間化簡（Polynomial   Reduction）的傳遞性（transitivity）  
   
  9。複雜類NPC：  
  定義一：如果語言L滿足  
  1.   L∈NP;  
  2.   對每一個L'∈NP，有   L'   <=p   L，即L是NP-hard的；  
  則稱L∈NPC  
   
  A   problem   Q   is   NP-hard   if   every   problem   P   in   NP   is   reducible   to   Q,   that   is   P   <=p   Q.  
  (which   means   that   Q   is   at   least   as   hard   as   any   problem   in   NP   )  
  A   problem   Q   is   NP-complete   if   it   is   in   NP   and   is   NP-hard.    
  (which   means   that   Q   is   at   most   as   hard   as   to   be   solved   by   a   polynomially   bounded   nondeterministic   algorithm)  
   
  注意:一個Np-hard的問題不一定屬於Np，譬如某問題L滿足每一個L'∈NP，有   L'   <=p   L;  
  但是該問題L不能在多項式時間內被驗證，則L是NP-hard的但是不屬於NP;  
  隻有當L是NP-hard且L∈NP，才有L∈NPC；  
   
  定理一：NPC=P   ←→   NP=P  
  定理二：B∈NPC且B   <=p   C   則C∈NPC；  
  定理二是用Polynomial   Reductions證明一個問題是NPC的依據；  
   
  10。SAT問題：  
  判斷一個布爾公式是否可滿足（即是否存在一組賦值使該布爾公式結果為true）。   SAT   =   {<φ>   |   φ是可滿足的布爾公式}  
   
  Cook’s   theorem:  
  The   satisfiability   problem   is   NP-complete  
   
  Reduction   as   tool   for   proving   NP-complete  
  Since   CNF-SAT   is   known   to   be   NP-hard,   then   all   the   problems,   to   which   CNF-SAT   is   reducible,   are   also   NP-hard.   So,   the   formidable   task   of   proving   NP-complete   is   transformed   into   relatively   easy   task   of   proving   of   being   in   NP.    
   
  Cook's   theorem的證明見《Introduction   to   the   Theroy   of   Computation》Chapter   8.4.3  
   
  11。3SAT問題：  
  “文字”是指一個布爾變量或布爾變量的非  
  “子句”是由∨連接起來的若幹文字；  
  一個布爾公式，若是由∧連接的若幹子句組成，則稱為合取範式(cnf)  
  若所有的子句都由三個文字，則稱為3cnf公式  
  3SAT={<φ>   |   φ是可滿足的3cnf公式}    
   
  定理：3SAT∈NPC  
  證明方法和SAT的證明類似；也可以利用邏輯公式的語法樹在多項式時間內構造一個等價的3cnf公式來證明；  
   
  證明一個問題Q屬於NPC的常用方法是證明3SAT問題可多項式化簡到Q；  
   
  12。證明一個問題Q是NPC的過程：  
  Prove   problem   Q   is   NP-complete,   given   a   problem   P   known   to   be   NP   -complete  
  For   all   R∈NP,   R   <=p   P;    
  Show   P   <=p   Q;       //   this   is   the   KEY   step  
  By   transitivity   of   reduction,   for   all   R∈NP,   R   <=p   Q;    
  So,   Q   is   NP-hard;  
  If   Q   is   in   NP   as   well,   then   Q   is   NP-complete.  
   
  13。幾種常見的多項式化簡  
   
  (1)   SAT     <=p   3SAT            
  構造原始公式φ的語法樹，引入中間變量yi作為每個內部節點的輸出，然後把原始公式φ改寫為根變量與描述每個頂點操作的子句的合取的“與”公式，這樣經改寫後的表達式為各個項的合取式，且每一項都有3個文字；然後將每一項變為由∨連接的子句，這可以通過窮舉每一項的三個文字的真值表做到（邏輯電路中的方法）  
   
  (2)   3SAT   <=p   CLIQUE   （EX13.18）  
  設φ是有k個子句的3cnf公式，歸約f輸出結果為，其中G是如下定義的無向圖：  
  中的每個節點分為k組，每組3個節點，稱為三元組t1,t2,..tk；每個三元組對應於φ中的一個子句，三元組中的每個節點對應於相關子句的一個文字；如果以下兩個條件同時滿足，我們就用一條邊連接兩個頂點u   和v：  
  1.u和v處於不同的三元組中；  
  2.他們的相應文字是一致的，即u所代表的文字不是v所代表的文字的非；  
  這樣很容易證明3SAT   <=p   CLIQUE  
   
  (3)   CLIQUE   <=p   VERTEX-COVER   (EX13.20)  
  利用補圖來進行化簡。對於一個無向圖G=(V,E)，定義G的補圖G'=(V,E')，其中E'={(u,v)|(u,v)不屬於E}。  
  化簡算法的輸入是CLIQUE的實例，它計算出G的補圖G'，這很容易在多項式時間內完成；化簡算法的輸出是VERTEX-COVER的實例。易證G具有一個規模為k的Clique當且僅當G'具有一個規模為|V|-k的Vertex-Cover；  
   
  (4)   VERTEX-COVER   <=p   SUBSET-SUM  
  化簡算法的核心在於圖G的關聯矩陣表示。  
  設G=(V,E)是一個無向圖，G的關聯矩陣是一個|V|*|E|的矩陣B，其中B[i,j]=1當且僅當頂點vi與邊ej向關聯，否則B[i,j]=0;  
  然後采用基數為4的方法表示數，具體過程比較複雜～～   ：（  
   
  (5)   SUBSET-SUM   <=p   JOB-SCHEDULING  
  設SUBSET-SUM實例為<{si},C>，並設S=∑si  
  構造一個JOB-SCHEDULING實例<{ti},   {di},   {pi},   k>   為   ：  
  if   S-C   <   0   ,   ti=2,   di=pi=1,   k=0  
  otherwise,   ti=pi=si,   di=C,   for   1<=i<=n,   and   k-S-C  
  下麵的過程顯而易見；  
   
  (6)   3SAT   <=p   HAM-CYCLE  
  核心是幾個特殊構造的“附件圖”，具體過程比較複雜～～  
   
  (7)   HAM-CYCLE   <=p   TSP     (EX13.11)  
  設G=(V,E)是HAM-CYCLE的一個實例，構造TSP實例如下：  
  建立一個完全圖G'=(V,E')，其中E'={(i,j)   |   i,j∈V   }，定義費用函數c為：  
  c(i,j)   =   0   ,   if   (i,j)   ∈   E;  
  c(i,j)   =   1   ,   otherwise  
  於是   就是TSP的實例；  
  易證G中具有哈密爾頓回路當且僅當G'中存在一條費用至多為0的TSP回路。  
   
  （注：EX13.12的證明：  
  隻要修改上述費用函數為c(i,j)=1,   if   (i,j)∈   E,   otherwise   c(i,j)=2,   得到的TSP實例為，  
  這樣即使當TSP的費用函數限製在{1,2}上他還是屬於NPC的   ）  
   
  (8)   HAM-CYCLE   <=p   UHAM-CYCLE