楔子
这学期选了中大的神课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$,是否存在哈密尔顿路径。