楔子
这学期选了中大的神课CSCI5320，授课老师是蔡雷震教授，香港一位很牛的搞算法的老师。蒟蒻被这门课虐得意识模糊，下周考试，复习之余写点心得。
P问题 NP问题 NPC问题 NP-hard问题 区别
几个问题介绍网络上很多，这里简单回顾一下：
$\rightarrow$ P问题：多项式可以得到解
$\rightarrow$ NP问题：多项式时间可以验证一个解的正确性
$\rightarrow$ NPC问题：又称NP完备。NP问题中最难的一类，也就是说任何NP问题都可以在多项式时间内归约到这一类问题上。
我们要证明一个问题A是NPC问题一般可以分为两步：
1）首先A是NP问题，那么给定一个解，可以在多项式时间内验证该解是否正确。（NP问题的要求）
2）其次找到一个NPC问题B，B可以多项式时间内归约到A。也就是说A比B难，可以通过解A，把B解了。
$\rightarrow$ NP-hard问题：比NPC更难，在多项式时间内无法验证一个解的正确性。
我们要证明一个问题A是NP-hard问题一般可以分为两步：
1) 对问题A给定限制条件得到一个特例B问题
2）证明问题B是NPC问题。
可以看出NPC是NP问题和NP-hard问题的交集。
举个例子：
Dense Induced Subgraph：给定图$G$，正整数$k$和$l$，是否存在$k$个点的生成子图包含最少$l$条边。
证明：令$l=C_k^2$，那么该问题变成Clique问题（NPC问题）
常见的NPC问题
$\rightarrow$ Clique
给定图$G$，正整数$k$，是否存在$k$个点的Clique。
$\rightarrow$ Vertex Cover
给定图$G$，正整数$k$，是否存在$k$个点的覆盖。
$\rightarrow$ Dominating Set
给定图$G$，正整数$k$，是否存在dominating set的大小最多为$k$。
Dominating Set $D$是点集$V$的一个子集，并且对于不在$D$中的点$v$，至少存在一条边$(u,v)\in E$，$u\in D$。
$\rightarrow$ Hamiltonian Cycle
给定图$G$
图$G$是否存在哈密尔顿回路$H$。
$\rightarrow$ 3-Satisfiability (3Sat)
给定一个有穷的布尔变量集合$X=\lbrace x_1,x_2,\ldots,x_n \rbrace$，变量$x_i$取值为1或者0，另有一组子句$C=\lbrace c_1,c_2,\ldots,c_m \rbrace$，$\mathbb{C}=c_1\wedge c_2 \wedge \ldots \wedge c_m$，$c_i = x_j \vee x_k \vee x_l$。求是否存在一组取值使得$\mathbf{C}$为真，即任意$c_i$为真。
$\rightarrow$ Independent Set
给定图$G$，是否存在Independent Set最少包含$k$个点。
$\rightarrow$ Hamiltonian Path
给定图$G$，是否存在哈密尔顿路径。