搜索控：NP完全问题

NP完全问题是学习算法分析遇到的概念，一般和P类问题、NP问题一起出场。我们老师当年已经在投影上打出了一大堆数学的推导公式来。我们先从他们的形式化定义中找到他们的关系，来直观地感受一下‘什么是什么’的问题。

1. 概念 P类问题就是在多项式时间内(O(n^k))可以解决的问题。这个好理解。 NP问题就是在多项式时间内可以被证明的问题。所谓的“可以被证明”的意思是可以在多项式时间内证明此问题能够解决，或者由此猜出问题的解。显然P类问题同时也是NP问题。而NP问题不是非P类问题。 那么有一类NP问题是决定性的，其他NP都能约化为这一类问题，这类问题就是NP完全问题。

2. 约化 那么什么是约化呢？一个问题约化为另一个问题的意思是，一个相对时间复杂度低的问题可以从一个相对时间复杂度高的问题中的解中得到自己的解，举例就是一元一次方程的解可以从一元二次方程的解得出。 通过约化的传递性也得出NP完全问题的定义。一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。

Reference:

1. matrix67上的《什么是P问题、NP问题和NPC问题》
2. Wikipedia上的NP完全问题
3. 《算法导论》P616

PS：搜索控系列是通过搜索引擎和浏览器标签获取到的知识在我脑中一刹那间的映射内容，文章内容也会不定期迭代式补充。