P问题，NP问题，NP完全问题，NP-hard问题
P问题NP问题NPC问题（NP-Complete）多项式规约深入理解NPC问题（NP-Complete）P=NP?第一个NPC问题Circuit Satisfiability（电路满足性问题） NPC问题的证明NP-hard问题常见的NP完全问题P问题
多项式时间可求解的问题，例如利用分治，贪心算法等能够求解的问题都是P问题。结果是positive的
NP问题
多项式时间可验证的问题。即这类问题可以被一个多项式时间的算法验证。
NPC问题（NP-Complete）
至今没有多项式时间算法可以解决它，结果是negative的
为了更好理解NPC问题，引入多项式规约（Polynomial Reductions)的概念
多项式规约
问题A多项式规约至B，记作A ≤p B （A,B皆视作问题集合）
如果问题A中的任何实例α都可以被转化为B中的一个实例β，且满足以下特征：
1.这个转化算法为多项式时间算法2.α的结果为yes当且仅当β的结果为yes
如果问题B是多项式时间可解的，那么问题A也是多项式时间可解的
如果问题A不是多项式时间可解的，那么问题B也不是多项式时间可解的
用集合来理解，问题A问题B都为集合，那么有：
即B中存在一个子集，使得子集里的实例可与A中实例一一对应。
用优化性问题与判断性问题来理解：
优化性问题常常可以简化成判断性问题来求解，下面给出一个简单例子：
可见，判断性问题在经过多项式时间算法后，可以转化成为优化性问题。
故而可以理解，问题B是更难解决的。 （A ≤p B ）
深入理解NPC问题（NP-Complete）
有了多项式规约的概念，再次深入理解一遍NP完全问题。给出下面的定义：
A∈NP对于任一问题B∈NP, 有B ≤p A
即，A∈NP问题集合中最难问题的集合（子集）
那么，NPC={A|A is NP-Complete}
所以，NPC是NP的子集。
再考虑一下P问题与NP问题的关系：
P问题是多项式时间可解的问题，NP问题是多项式时间可验证的问题。
那么有P⊆NP，多项式时间可解的问题总是多项式时间可验证的，多项式时间可验证的问题就不一定是多项式时间可解的。
于是有下图的关系：
P=NP?
P是否等于NP还是未知的
第一个NPC问题
我们将计算机看作是可以求解任何问题的，那么将计算机可解决的问题抽象出一类问题，就有任何问题都可以规约成计算机可解决的问题。即，任何问题 ≤p 计算机可解决的问题。
Circuit Satisfiability（电路满足性问题）
电路满足性问题是第一个NPC问题，也就是通过与、或、非门，可以实现多个输入（无论是0或1）都能得到一个输出1
有了第一个NPC问题，那么其他NPC问题也就能相应地找出来。
NPC问题的证明
若想要证明问题Lnew是一个NP-Complete问题
证明Lnew∈NP选出一个相应的老问题Lknown设计一个多项式时间算法使得对于每一个老问题的实例，都能转化成新问题的实例。证明老问题的实例结果为yes当且仅当新问题的实例结果为yes
即，Lknown ≤p Lnew
那么，可证新问题Lnew是一个NP完全问题。
注：一定是老问题规约到新问题，才得证新问题为NP完全问题。顺序不能搞反
NP-hard问题
在证明过程中，由于第一步证明Lnew∈NP，即新问题是多项式时间可验证的。该步骤很容易证明，若省略的话，则得到的Lnew称为是NP-hard问题。
常见的NP完全问题
最大团问题（Clique）、顶点覆盖问题（Vertex-Cover）
旅行商问题（Traveling-Salesman）、哈密顿回路问题（Hamiltonian-Cycle）
其中，顶点覆盖问题可由最大团问题规约，旅行商问题可由哈密顿回路问题规约
