NP-hard vs NP-Complete

判断一个问题是不是NP-Complete有两个步骤：

1. 判断是否NP，就是算法结果的正确性能不能在多项式时间内验证
2. 判断是否NP-hard，要判断NP-hard，我们可以使用一个叫Reduction的技巧。直观来说，如果你能用你的问题的求解器来求解另一个已知是NP-hard问题，那么你的问题也是NP-Hard的。

Reduction

Reduction是将两个算法建立联系的一个过程。我们说X reduce 到Y，意味着，假设现在有一个Y的黑盒求解器，于是我们设计一个多项式算法来用Y的求解器来求解问题X。
也就是说，当这个求解器是多项式时间的时候，意味着X也可以多项式求解。那如果我们已经知道X是很难求解，如果X可以reduce到Y，那么意味着Y跟X一样难解，因为只有困难的求解器才能解决困难的问题。
而这正是证明问题Y是NP-hard或NP-complete的思路，只要找到一个Np-hard或者NP-complete的问题X可以reduce到Y就可以了。

那么NP-hard是什么？

如上图，在所有NP(non-deterministic polynomial-time)问题中（结果正确性可以在多项式时间验证），有些问题是特别难的，如NP-complete问题，有些问题很简单，如P问题，可以在多项式时间解决。

那如果我们找到一个特别的问题H，使得所有NP问题都可以reduce到问题H上，那这个问题H肯定特别难，因为我们能用这个问题H解决所有的NP问题，因此我们称这个问题H为NP-Hard问题。

这个经过reduce的问题H不一定是NP问题，于是才有上述示意图的上部分，即有一部分NP hard问题是落在圈外的。如果问题H是属于NP的话，那么问题H就是NP-complete问题，NP完全是NP和NP-hard的交集。

NP定义: 可以在多项式时间验证结果正确性的问题。
NP-hard定义: 对于问题H，所有NP问题都可以reduce到H。

这意味着，如果NP-hard可以用多项式解决，那么所有NP问题都可以用多项式解决。不过目前还没人找到多项式算法。

SAT Problem

在实际中，我们判断一个问题是不是NP-hard，通常不会去根据这个定义来判断，而是使用Reduction来判断，就是找到一个已经被证明是NP-complete的问题，然后尝试reduce。

总的来说，判断一个NP问题是不是NP-Complete的两个方法

1. 找到一个NP-Complete问题，经过证明可以reduce to 你的问题，这意味着你的方法可以解决这个NP-Complete问题，那很显然，这个解决方法也是NP-Complete的。
2. 所有的NP问题都可以reduced到你的问题

很显然，方法1简单多的，我们只要找到一个现成的 NP-Complete问题就可以了，然而，这个世界上，总得有第一个NP-Complete问题才能够用这个方法，这第一个NP-Complete问题的证明，注定了只能用方法2，那就是要证明所有NP问题都可以reduced到这个问题上，而万幸的是这第一个NP-Complete问题在40年前被找到了，它就是著名的SAT问题。

SAT实际上并没有真的遍历所有的算法一个个去reduce，相反，他证明了所有的算法都是可以编码为boolean formula问题，这意味着所有算法都可以使用SAT的求解器去求解，因为他们本质上就是boolean formula问题。至于怎么证的，太难了这里就不讲了。

现在我们介绍一下SAT问题。对于任意的boolearn foumula我们总能写成以下标准式：
$$(..\vee ...\vee ..)\wedge (..\vee ...\vee ..)\wedge ...$$
其中$\vee$表示或，$\wedge$表示与。上述表达式是很多个$\wedge$并在一起的，所以我们称每一个$(..\vee ...\vee ..)$都是一个Clause. 接下来举个例子:
$$\left(x_1\vee \overline{x_2}\vee x_3\right)\wedge \left(\overline{x_1}\vee x_2\right)\wedge \left(\overline{x_2}\vee x_3\right)$$

上面的每个$x_1,x_2,x_3$只能取0,1两个值，加上一个横线表示取非，那么当$x_1,x_2,x_3$取什么值的时候，这个公式为真？或者根本不存在一个取值使公式为真？这就是SAT问题。最后这道题答案是x1=0,x2=0,x3=任意。一个更简单的问题是3-SAT问题，每个clause恰好都有3个元素，可以证明这个3-SAT也是NP Complete的。

Reducing SAT to Shortest Clique Problem

接下来介绍Reduction到底是怎么使用。首先Clique问题就是找到一个图大小为k的团，其中团是一个完全图（每个结点相互联结）。
考虑以下 bool formular，在什么情况下才是真？

$$\left(x_1\vee \overline{x_2}\vee x_3\right)\wedge \left(\overline{x_1}\vee x_2\right)\wedge \left(\overline{x_2}\vee x_3\right)$$
这个公式只有在3组clause中，每组取1个变量，这3个变量同时为真的时候才成立。那么找到“三个变量同时为真”，不相当于一个大小为3的团吗？

为了体现这点我们构造一个图，每个clause作为一组结点，分别有3组，并与其他组之间的结点连线，注意，因为我们需要3个变量同时为真，所以，不可以同时为真的结点不可以连线，比如$\overline{x_2},x_2$是没有连线的，那么只要我们在三组变量之间找到一个团，就可以同时设这3个变量为1，也就找到了这个bool formula的解了。

Reducing SAT to Shortest Tour Problem

Shortest Tour 问题就是如何找到一条最短路径，访问所有的结点并回到原点。

现在构造一个特殊的结构：

从A到B的最短路径有多少条？答案是只有两条，不管我们怎么加长这个结构，也是只有两条。为了将SAT跟 Shortest Tour 联系起来，直觉来看，我们似乎可以利用选择选择哪条路径来表达 真还是假。

如果我们将这些结构复制n份然后连起来

那么一共就有$2^n$条可能的路径。那么每一份路径就表示一个true或false。现在x1,x2,…,xn有了，那么怎么将他们组合起来形成clause呢？

假设有一个clause就是$...\wedge x_2\wedge ...$,很显然这个clause意味着x2一定要等于true，那么就相当于下图，额外加了一个结点，强制让x2只走那条等于true的路。

同理对于一个更复杂的clause，就是连接多条边。只要x1 x2 x3其中有一个经过下面clause的结点，那么这个clause就为真，如果一共有m个clause，我们就可以构造出m个这样类似的结点，如果能找到一条最短路径，使得他经过所有的clause结点，那么这个bool formula就一定为true.

A List of NP-Complete

为了证明一个问题是NP complete我们有必要去了解更多的NP complete问题以方便证明，不然每次都只用SAT去证也是挺困难的事情。wiki上有一个列表，基本上很全了：List_of_NP-complete_problems

这里拿一些经典问题来介绍一下。

Set Vertex Cover Problem & Independent Set

最大独立集和最小结点覆盖其实是两个互补的问题。
所谓independent set就是在集合中，每个结点都不会相互连接。上图结点 {3, 4, 5} 是一个大小为3的 independent set 而 {1, 4, 5, 6} 则是最大的 independent set。

而Vertex Cover就是找到一个结点集合使得图上的每一条边的至少一端是在集合中。在上图结点{2, 3, 7} 就是最小的覆盖结点，大小为3。

显然{2, 3, 7}恰好跟最大独立集 {1, 4, 5, 6}互补。这是因为在independent set中，任意2个结点<u,v>都不会有一条边相连，所以与u,v相连的结点一定在集合外面，所以independent set的补集一定是vertex cover的。

K-coloring and Clique

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P0oVTu20-1576142062972)(https://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/330px-Petersen_graph_3-coloring.svg.png)]
染色问题就是找到一种染色方式，使得邻居的颜色都不一样。
染色问题跟找团问题是很相近的，考虑一下两个问题：

1. 如果一个图包含一个大小为k的clique，那么需要多少种颜色？
2. 如果一个图最多需要k种颜色，那么最大团的大小是多少？
   他们的答案都是k。因为jk-color问题要求所有邻居的颜色不同，而团正是这种相互邻居的数量。

Packing

这个问题就是给你一定容量和形状的容器，怎么装上价值最高的东西，又或者是装尽可能多的东西，这问题有很多变种。

Longest Common Subsequence

有两个字符串：

1. lemonade
2. blendev
   他们最大的公共的序列是什么？注意，这个序列是不需要连续的（连续的叫substring，它不是np hard问题），可以中间跳过一些元素，而且序列的个数是任意的，如果是确定的话，比如已知只有两个，那不是np-hard，而可以用动态规划求解。
   显然这个字符串最大公共部分是: lende

参考资料

https://classroom.udacity.com/courses/cs313/
wiki: NP-hardness
Algorithm design - Jon Kleinberg, Éva Tardos

附录

Big O Notation

影响一个算法的速度的因素有非常多，输入的大小，电脑的速度，内存大小，算法使用什么语言来实现等等，因此想要分析算法，我们要做几个简化的假设来忽略掉不必要的细节。

假设有两个算法，他们的最坏运行时间分别为，A:$3n^2-n+10$,B:$2^n-50n+256$，其实我们并不关心里面常数项的大小，很显然当n足够大的时候，算法A要比算法B块。基于此我们可以定义一个大O符号来表达这种关系。
大O的定义：我们称$f(x)=O(g(x))\text{ as }x\to \infty$,当且仅当，存在一个实数M，使得
$$|f(x)|\le Mg(x)\text{ for all }x\ge x_0.$$
话句话说，大O表示了一种上界，举几个例子。$n+1=O\left(n^2\right)$,$n^2+n+1=O\left(n^2\right)$。对于算法而言，我们一般使用算法的最坏时间复杂度作为f(x)，然后再求出其g(x),在算法中，一般假设内存读取时不需要运算时间的，只有运算的时候（加减乘除判断大小）才会算次数。举个例子，

result=0
for i in range (0,n):for j in range(i,n):result=result+1

该算法的运行时间为$3\ast (n+n-1+...+2+1)=3\ast \frac{n^2+n}{2}=O\left(n^2\right)$,每次for循环以及最后的加法都是需要消耗计算资源的，所以3是这么来的。