【NPC】1、NP、P、NPC概念介绍
一、P、NP、NPC概念
1971年，Stephen Cook和Leonid Levin提出了第一个NPC问题：布尔可满足性问题。1979年，Garey和Johnson出版了一本书：“Computers and Intractability: A Guide to NP-Completeness”，中文版是“计算机和难解性”，在这本书中提出了“6个基本的NPC问题：3SAT、顶点覆盖、团、三维匹配、汉密尔顿回路、划分问题”。
P问题：我们以前接触过的算法如：图搜索问题、最短路径问题、最小生成树问题，都是能够在多项式时间内解决的决策问题，我们把这些问题称为P问题。P问题是集合的集合，因为P={最短路径问题、最小生成树问题、...}，而最短路径问题又是一个集合。
NP问题：多项式时间内能够验证的问题称为NP问题。验证（Verify）的意思是：给定一个问题的实例（Instance）、证书（Certificate，证书就是类似于证据），需要验证这个证书是这个问题的正确答案。比如汉密尔顿路径问题，实例为G=(V,E)，证书为顶点序列 {v0,v1,v2,v3,....,vk}，我们的目的是要验证这个证书就是这个问题的答案，验证方法为：先遍历一遍这个点序列，看看是不是每个点只出现一次，然后对于(vi,vi+1)是否为G的边，这样就能够验证这个点序列是不是汉密尔顿路径，很显然这个验证过程是多项式时间的，所以汉密尔顿路径是NP问题。
(1)P问题是不是NP问题呢？很显然是，因为我们如果要验证一个P问题，只需要给一个实例和一个空的证书（即不需要给证书），直接求解P问题即可，所以也是多项式时间能验证的。(2)P是不是等于NP呢？目前的答案是“不是”，但是还不能证明，因为NP中还有一类NPC问题，如果我们能够证明NPC是P问题，则NP=P。
NPC问题：目前不能用多项式时间解决的问题，但是我们还不能证明这个问题不能用多项式解决，我们这次的目标是研究这个问题。NPC的定义：
NP难问题：如果一个问题不满足NPC的第一个条件，只满足NPC的第二个条件，则称为NP难问题。
二、规约
规约（Reduction）：如果我们要证明一个问题A是NPC问题，则只需要首先证明他是NP问题，然后只要找一个你所知道的NPC问题规约到A即可。规约类似于函数调用，比如要将A规约到B，则只要：function A(....) //一系列变换
B(....);
因此我们在证明一个问题是NPC问题时，如果掌握的已知NPC问题越多，对于你的规约越有利。
一般来说证明B是NPC的过程如下：
1.证明B是NP问题。2.知道一个已知的NPC问题A。3.给出一个规约过程，并证明此规约过程是多项式时间的。对于A中的任意一个实例：4.如果A有一个真的实例，则B也有一个真的实例。5.如果B有一个真的实例，则A也有一个真的实例。
接下来的文章也是按照这个方式来证明的。
总结一下P、NP、NPC的关系如下：
