第9章 图论算法

网上有一篇介绍NP的文章挺不错的

总结一下：
1、如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
2、在多项式时间内验证一个解是否正确的问题称为NP问题（当然，所有的P类问题都是NP问题）
3、同时满足下面两个条件的问题就是NPC问题
  （1）它得是一个NP问题
  （2）所有的NP问题都可以约化到它

4、NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（所以NP-Hard不是NP问题）