[Udacity CS 215] Algorithms (Week #6)

  
previously:
第五个unit  http://www.1point3acres.com/bbs/thread-37701-1-1.html
第四个unit  http://www.1point3acres.com/bbs/thread-37651-1-1.html
第三个unit  http://www.1point3acres.com/bbs/thread-37565-1-1.html
第二个unit  http://www.1point3acres.com/bbs/thread-37403-1-1.html
第一个unit  http://www.1point3acres.com/bbs/thread-37390-1-1.html


这门课的副标题是crunching social networks，跟图有关的各种算法前面几章都已经讲完了。简单的复习一下：
第一章讲了欧拉回路；第二章讲了怎么样构造表示图；第三章讲了连通分量、二分图、割边、图遍历；第四章讲了centrality和topK问题；第五章讲了最短路径。
而本章的标题是Hardness of network problems，讲NP理论。虽然这个topic每门算法课都要讲，其实是一个很学院派的话题。

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有硬搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有硬搜才行”的问题，NPC问题才是。

首先解释一下什么是NP问题，什么是NP完全问题。
P Problem：
这个应该最易理解，就是一个问题可以在Polynominal的时间的得到解决，当然，是对于任意input size。
NP Problem：
对于一类问题，我们可能没有一个已知的快速的方法得到问题的答案，但是如果给我们一个candidate answer，我们能够在polynominal的时间内验证这个candidate answer到底是不是我们已知问题的答案，这类问题叫做NP problem。所以很显然 P Problem是NP problem的一个子集。

NP问题是指可以在多项式的时间里验证一个解的问题。比如，Hamilton回路就是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。 另外，如果把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就连在多项式的时间里验证都不行了，因为要验证它除非你试过所有的路，所以这就已经不是一个NP问题了。

NP-complete Problem：
对于这一类问题，他们满足两个性质，一个就是在polynomial时间内可以验证一个candidate answer是不是真正的解，另一个性质就是我们可以把任何一个NP问题在polynomial的时间内把他的input转化，使之成为一个NP-complete问题。

为了说明NPC问题，我们要引入一个概念——归化(Reduction)。
    简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A。《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。

如何判断一个问题是不是NP问题：

- has a short accepting certificate
- exsits a verification polynominal algorithm

如何判断一个问题是不是NPC问题：

根据NPC问题的定义：首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。所以，证明NPC问题先得证明它至少是一个NP问题（两个性质），再证明其可以从中一个已知的NPC问题能约化到它。历史上第一个被证明是NPC的问题就是SAT问题。讲义里有个例子，把着色问题归化到SAT问题，证明出着色问题就是NP问题。
  
  
编程作业题：

---

Programming a Reduction

写一个python程序，把Independent Set Problem 归化到 Clique Problem。
（反过来，证明分团问题(clique problem)是NPC可以从独立顶点集问题（Independent set problem）归化。因为存在一个大小是k以上的clique等价于它的complement graph中存在一个大小是k以上的Independent set。）