了解P/NP问题
前置知识
- 时间复杂度：一般用O(n)这样的形式表示。并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
- 多项式(polynomial)复杂度：如果时间复杂度可以表示成多项式形式(规模n不作为指数，作为底数)，例如O(n^2)。这种多项式时间复杂度一般是认为计算机可以承受的；如果复杂度是非多项式的话，例如O(n!)或者O(2^n)，则基本上认为大规模下计算机是不可计算的。所以这也衍生到我们需要寻求多项式复杂度的算法。
为了表示一个问题是否有多项式解，我们就可以得到如下的几种问题类型。
P问题
P就是多项式英文单词的首字母，很好记忆。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题，例如寻找[1,n]之间的偶数就是一个多项式问题，时间复杂度为O(n)
NP问题
NP容易被误解成非多项式问题，其实不然。NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。就是说这个问题，至少告诉你一种解法，你可以在多项式时间内验证他是正确的。NP问题可以是一个P问题，也可以不是一个P问题；所有的P类问题肯定是个NP问题。之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。
NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。P=NP证明和证伪现在仍然是世界七大数学难题。
NPC问题
c是compelete完全的意思。先理解一个概念：
- **约化(Reducible): **如果我们说问题A可约化为问题B，那么B的时间复杂度高于或者等于A的时间复杂度。找到解决B问题的解也可以用来解决A问题。例如你可以解一元二次方程，那么自然也可以解一元一次方程(一元二次方程的二次项系数为0即可转化)。约化具有传递性。
- 多项式约化：要对于解决问题有帮助，这种约化肯定是需要在多项式内时间完成才有意义，所以寻找解决问题的约化肯定是寻求多项式约化。
NPC 问题定义为同时满足如下两个条件的问题。首先，它必须是一个 NP 问题；然后，所有的 NP 问题都可以约化到它。
假设NP=P，则找到一个NPC问题的解等于解决了所有的NP问题，也就是等于解决了所有P问题。如果能在多项式内解一个NPC问题，你等于可以解决世界上所有的问题，听着有点玄乎。因此，有不少人还是认为NP=P不成立的。
现在NPC问题还没有有效的多项式解法，这些NPC问题的列表有兴趣可以参考下wiki百科，比较为人所知的NPC问题就是Hamilton回路问题了。大体上把这些问题做了一些分类，互相之间可以互相转化：
NP-Hard问题
NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。几个问题的图可以参考如下。根据NP是否等于P这个图有两种画法。NPC问题无论在哪种情况下，可以认为是NP-hard问题的一个子集。
