如何证明NP-Hard Problems

【1】 经典问题：电路可满足性问题 The circuit satisfiability problem asks, given a circuit, whether there is an input that makes the circuit output TRUE, or conversely, whether the circuit always outputs FALSE.

【2】

• P: can be solved in polynomial time
• NP: If the answer is YES + this fact that can be checked in polynomial time
• co-NP: If the answer is NO + this fact that can be checked in polynomial time

【3】

• NP-hard: no one in their right mind should believe a np-hard problem can be solved in polynomial time.—所有的NP问题都能约化到他，但他本身不一定是个NP问题

Π is NP-hard ⇐⇒ If Π can be solved in polynomial time, then P=NP

• NP-complete:( the hardest problems in NP) it is both NP-hard and an element of NP. —所有的NP问题都能约化到他，而且他本身也一定是个NP问题
• 所以：NP-Hard问题要比 NPC问题的范围广

P问题就是指该问题能在多项式复杂度内解决。

NP问题就是指该问题能在多项式复杂度内被验证。

复杂度一般用大写字母O表示，多项式复杂度记为O(n(^k))。

NP-hard问题就是比NP问题更困难解决的问题，通常NP问题都可以说是NP-hard问题，但是不是所有的NP-hard问题都是NP问题（有些NP-hard问题无法被验证）

NP-complete（NPC问题）就是既是NP问题也是NP-hard问题。

链接：https://www.jianshu.com/p/9cad6175a1ea  

The Cook-Levin Theorem：Circuit satisfiability is NP-complete.

【4】reduction：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可归约为问题B。(一个问题归约为另一个问题，时间复杂度增加了，问题的应用范围也增大了)

如何证明一个问题是NP-hard? To prove that problem A is NP-hard, reduce a known NP-hard problem to A.

boolean formula 形如： 要使整个formula的结果是TRUE，则每个clause的值都为TRUE，那么每个clause里的元素只需要有一个是TRUE，那么最终的结果就是TRUE。

SAT问题 已知电路可满足性问题（CSAT）是NP-hard，找到一个变化法则将CSAT约化成SAT，那么既然CSAT是NP-hard,则可证明SAT是NP-hard。 可以通过上图所示深度优先搜索的方式，在线性时间O(n)内将任何 boolean circuit 转化成 boolean formula，Tus，we have a polynomial-time reduction from CSAT to SAT:

SAT is NP-complete.

【5】 3SAT：3SAT is just SAT restricted to 3CNF formulasprove that 3SAT is NP-hard ： 虽然已经证出SAT是np-hard，但CSAT更容易理解，所以证明3SAT是np-hard依然是找到一个变化法则将CSAT直接约化成3SAT，只是在将 boolean circuit 转化成 boolean formula时，保证每个clause里只有三个元素 四步走可以完成：

1. Make sure every AND and OR gate has only two inputs. If any gate has k > 2 inputs, replace it with a binary tree of k−1 two-input gates.
2. Write down the circuit as a formula, with one clause per gate. This is just the previous reduction.
3. Change every gate clause into a CNF formula.
4. Make sure every clause has exactly three literals.

通过以上步骤由boolean circuit 转化成的3CNF formula，最终结果看起来体型非常庞大，但他仍然只是一个常数因子，并且这个约化过程可在多项式时间内完成。

3SAT is NP-complete.

【6】 Maximum Independent 从无向图中的顶点中选出k个并且k个顶点之间互不相邻，最大的k就是最大独立集（ MAXINDSET）

证明MAXINDSET是NP-hard： reduction from 3SAT 在多项式时间内，将3CNF formula reduce to 一个无向图，找到使3CNF formula为TRUE的安排，则可找到该无向图的最大独立集，即可证明。 转换规则： 1）formula里出现的每一个字母，图中都有对应的节点 2）在同一个clause里的字母用一条边连接 3）变量（字母）和其逆用一条边连接（如x和x ） 证明过程： 一个3CNF formula： 转换成一个无向图： 设3CNF formula有k个clause，则对应的无向图的最大独立集为k分析： independent set ⇒ satisfying assignment:最大独立集的顶点之间没有边，所以他们不可能在一个clause里，且不会互逆（互逆的都用边连起来了），将最大独立集中的所有节点值都设为TRUE，则对于原来的3CNF formula来说，每一个clause都是TRUE，则整个formula的值也是TRUE。

satisfying assignment ⇒ independent set: 这个更好理解，由formula为TRUE推到存在这样的一个无向图的最大独立集，将每个clause里选一个字母取真即可（因为按照上面的规则，一个formula一定可以转成一个无向图）

【7】 Clique 从无向图的顶点集中选出k个并且k个顶点之间任意两点之间都相邻（完全图），最大的k就是最大团（MAXCLIQUE）证明 MAXCLIQUE是NP-hard： reduction from MAXINDSET 为找出最大独立集与最大团的关系，取上文中给出的例子前两个clause举例： 按照规则得出的无向图G如下： 则对应的边补图G’如下： 所以很容易发现，在每个clause里取一个即为图G的最大独立集，同时也是图G’的最大团，中间只需要一个多项式时间内的边补图转化。

【8】Vertex Cover 找到一个结点集合使得图上的每一条边的至少一端是在集合中

在independent set中，任意2个结点都不会有一条边相连，所以与u,v相连的结点一定在集合外面，所以independent set的补集一定是vertex cover的，显然，independent set和vertex cover其实是两个顶点互补的问题

【9】K-Coloring 找到一种染色方式，使得每一条边两个顶点的颜色都不一样证明3COLORABLE is NP-hard： reduction from 3SAT 在多项式时间内，将3CNF formula reduce to 一个无向图，找到使3CNF formula为TRUE的安排，则可找到该无向图的3-coloring染色方式。 染色规则： 1）truth gadget ：三个顶点均有边相连，需要三种颜色，三种颜色的名字就叫Ture,False,Other（任何一种颜色） 2）variable gadget：由上图，所以a和a逆的颜色只能是true,或false 3) clause gadget： a clause gadget for (a∨b∨c逆). 所以，已知一个3CNF formula为TRUE，可以由以上规则得到一个被染色的图；已知一个3-coloring的图，可以根据上述方式反推到一个值为TRUE的3CNF formula

【10】Hamiltonian Cycle （？） 给定一个图，判定是否有经过图中每个顶点且仅一次的回路证明Hamiltonian Cycle is NP-hard： reduction from vertex cover 思路：已知一个图G和一个整数k，我们将其转换为另一个图G’，这样，当且仅当G的顶点覆盖为k时，G’才具有哈密顿环 转换规则： 对于原来图G中的每条边，我们在G’中用形式如下的edge gadget对应:

【11】 Subset Sum 给定一组整数X和一个整数t，确定集合X里是否具有其元素总和为t的子集。证明Subset Sum is NP-hard： reduction from vertex cover 思路：给定一个图G和一个整数k，我们需要将其转换为一个整数集合X和一个整数t，这样，当且仅当图G的顶点覆盖为k时，集合X的子集总和为t。转换规则： 1）将图G的边从0到m-1任意编号，对于每一条边i,集合X中有一个对应的整数 bi ，定义为4的i次方；对于每一个顶点v在集合中对应的整数ai,定义为：（dalta（v）是所有端点有v的边的集合） 即：集合X里，元素都是以4为底的 2）如果第m个整数表示顶点，则数字值为1，否则为0。对于i