【算法】P问题，NP问题，NPC问题（NP完全问题），NP-hard问题

多项式时间可求解的问题，例如利用分治，贪心算法等能够求解的问题都是P问题。结果是positive的

多项式时间可验证的问题。即这类问题可以被一个多项式时间的算法验证。

至今没有多项式时间算法可以解决它，结果是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 ）

有了多项式规约的概念，再次深入理解一遍NP完全问题。给出下面的定义：

即，A∈NP问题集合中最难问题的集合（子集）
那么，NPC={A|A is NP-Complete}

所以，NPC是NP的子集。

再考虑一下P问题与NP问题的关系：
P问题是多项式时间可解的问题，NP问题是多项式时间可验证的问题。
那么有P⊆NP，多项式时间可解的问题总是多项式时间可验证的，多项式时间可验证的问题就不一定是多项式时间可解的。

于是有下图的关系：
在这里插入图片描述

P是否等于NP还是未知的

我们将计算机看作是可以求解任何问题的，那么将计算机可解决的问题抽象出一类问题，就有任何问题都可以规约成计算机可解决的问题。即，任何问题 ≤p 计算机可解决的问题。

电路满足性问题是第一个NPC问题，也就是通过与、或、非门，可以实现多个输入（无论是0或1）都能得到一个输出1
在这里插入图片描述
有了第一个NPC问题，那么其他NPC问题也就能相应地找出来。

若想要证明问题Lnew是一个NP-Complete问题

即，Lknown ≤p Lnew
那么，可证新问题Lnew是一个NP完全问题。
注：一定是老问题规约到新问题，才得证新问题为NP完全问题。顺序不能搞反

在证明过程中，由于第一步证明Lnew∈NP，即新问题是多项式时间可验证的。该步骤很容易证明，若省略的话，则得到的Lnew称为是NP-hard问题。

最大团问题（Clique）、顶点覆盖问题（Vertex-Cover）
旅行商问题（Traveling-Salesman）、哈密顿回路问题（Hamiltonian-Cycle）
其中，顶点覆盖问题可由最大团问题规约，旅行商问题可由哈密顿回路问题规约