P问题、NP问题、NPC问题的概念即实例证明
几种问题及其关系
首先解释一下什么是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问题的一种常用方法，通常用&=这个符号来表示。如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的时间内完成），
1. 把P的输入转化到Q的输入；
2. 把Q的输出转化到P的输出。
下图展示了上述规约过程。其中T1 在多项式时间将 P的输入Pinput 转化成Q的输入Qinput ; T2在多项式时间将 Q的输出Qoutput 转化成P的输出Poutput 。
如何对问题证明
下面来列出了一些常见的证明问题及其证明套路。
证明NP问题。这个容易，即给你一个结果，你能在polynomial的时间内验证该结果的正确性。 证明NP-hard问题。我们要证明一个问题是NP-hard的时候，我们通常要做的是找到一个已被证明了的NPC问题，并把这个NPC问题归约到该问题上去（即NPC&=NP-hard）。 证明NP-Complete问题。分以下两步：
第一步证明这个问题属于NP； 第二步，证明这个问题是NP-hard的。
下图列出了几个已被发现NP-Complete问题（更全面的NP-Complete问题列表。可以看出所有的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
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)
vcqxvOShozwvcD4NCjxzdHJvbmc+sNFQtcTK5Mjr16q7r7W9UbXEyuTI6zwvc3Ryb25nPqO6PHN0cm9uZz5QtcTK5MjrPC9zdHJvbmc+ysew/LqsPG5vYnI+bTwvbm9icj649mNsYXVzZbXEM1NBVLHttO/KvaO7PHN0cm9uZz5RtcTK5MjrPC9zdHJvbmc+tbHIu8rH16q7r7XDtb21xM280M48bm9icj5HPC9ub2JyPtLUvLC2wMGivK+1xLTz0KGyzsr9PG5vYnI+Zz1tPC9ub2JyPqGjIDxzdHJvbmc+sNFRtcTK5LP216q7r7W9ULXEyuSz9jwvc3Ryb25nPqO6PHN0cm9uZz5RtcTK5LP2PC9zdHJvbmc+ysc8bm9icj5HPC9ub2JyPrXE0ru49rTz0KHOqjxub2JyPmc8L25vYnI+tcS2wMGivK+juzxzdHJvbmc+ULXEyuSz9jwvc3Ryb25nPsrHM1NBVLXE0ru49riz1rWho7zZyeg8bm9icj5HPC9ub2JyPtbQ09DSu7j2tPPQoc6qPG5vYnI+bTwvbm9icj61xLbAwaK8r6Os1PLSu7aoyscxKcj9vcfQzsTasr/I/bj2tqW149a7xNzIodK7uPYgMimyu8r009rI/b3H0M61xLHfy/nBrL3TtcS2pbXj0rLWu8ih0ru49qGjttTT2sO/uPZjbGF1c2WjrMjnufvRodTxwcs8bm9icj54PC9ub2JyPrbU06a1xLalteOjrNTywe48bm9icj54PTE8L25vYnI+o6zI57n70aHU8cHLPG5vYnI+eKGlPC9ub2JyPrbU06a1xLalteOjrNTywe48bm9icj54oaU9MTwvbm9icj4uINTyuMO4s9a1ysfC+tfjtcShow0KPGg0IGlkPQ=="2-3sat-vertex-cover">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)。
假设有一个满足的3SAT的赋值，对于二元点对，如果xi=1，则将xi加入顶点集S，否则将xˉi加入顶点集S；对每一个clause对应的三角形顶点，如果选择该clause中的xi=1，则与该顶点没有连接的三角形的2个顶点加入顶点集S。则最终得到的顶点集S是一个覆盖，容易知道该顶点集内顶点个数是n+2m。如上图中是赋值x1=x2=x3=x4=1，第一个clause选择了x1=1，第二个clause选择了x2=1。
假设有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的输入是包含mm个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的大小为kk的独立集。 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 ，由于u,v为相邻节点，故为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。