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
请阅读更多我的博客文章>>>