NP-hard问题证明

NP-hard问题：比NPC更难，通常在多项式时间内无法验证一个解的正确性。几个复杂度的区别可以看NPC介绍。

常见证明

我们要证明一个问题A是NP-hard问题一般可以分为两步：

1) 对问题A给定限制条件得到一个特例B问题    
2）证明问题B是NPC问题。

以下罗列四个较直观简单的例子：

  1. Dense Induced Subgraph

    问题：给定图$G$，正整数$k$和$l$，是否存在$k$个点的生成子图包含最少$l$条边。
    证明：令$l=C_k^2$，那么该问题变成Clique问题（NPC问题）
    解释：$k$个点的完全子图最多的边包含$C_k^2$，所以当$l=C_k^2$，那么原问题变成寻找$k$个点的子图且是完全图，那么就是Clique问题。

  2. Edge Packing

    问题：给定图$G$，正整数$k$和$l$，图$G$是否存在$l$条边与最多$k$个点相邻。
    证明：令$l=C_k^2$，那么该问题变成Clique问题（NPC问题）
    解释：$k$个点的完全子图最多的边包含$C_k^2$，那么当$l=C_k^2$，最少需要$k$个点，此时原问题变成Clique问题。

  3. Hitting Rectangles

    问题：平面上有一组长方形$R$，一组点$P$，和一个正整数$k$，是否可以从$P$中选择$k$个点，使得任意一个长方形上都有点。
    证明：特例是点覆盖。
    解释：绘制一个图G，$u$和$v$是$P$中的两个点，$u$和$v$之间如果有边，则表示一个长方形。那么在这种情况下，需要覆盖所有的边，该问题就成了点覆盖问题。

  4. Eulerian Subgraph

    问题：给定图$G$，正整数$k$，图$G$中是否存在Eulerian子图恰好包含$k$条边。
    证明：对于Cubic Graphs(所有点的度都等于3)，令$k=n$，那么该问题就等价成哈密尔顿回路问题，是NPC复杂度。
    解释：$k=n$时，可以证明所有的点都只经过一次，因为每个点的度数都不超过3，如果经过两次，度数就为4。