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