数据结构与算法设计分析——NP完全理论

一、P类问题与NP类问题的定义

P类问题与NP类问题是计算机科学和数学中的两类重要问题，简单的来说，P类问题是较“容易”的问题，在计算机中，可以在多项式时间内解决，而NP类问题是较“复杂”的问题，它并不能在多项式时间内解决，只能验证是否存在解（解是否正确）。

常见的P类问题有排序、搜索算法等等，但不是所有的排序算法都是P类问题，例如，下表中快速排序、堆排序和归并排序是P类问题，其平均时间复杂度呈多项式，由于插入排序、冒泡排序、简单选择排序的平均时间复杂度都呈指数级，所以不属于P类问题，而是NP类问题。

排序名称	平均时间复杂度
直接插入排序	O(n2)
折半插入排序	O(n2)
希尔排序	依赖于增量序列
冒泡排序	O(n2)
快速排序	O(nlog2n)
简单选择排序	O(n2)
堆排序	O(nlog2n)
归并排序	O(nlog2n)

二、常见的NP类问题

（一）旅行商问题（TSP）

旅行商问题中给定一组城市和每对城市之间的距离，寻找一条最短路径，使得旅行者能够遍历所有城市并回到起始城市。
由于该问题的复杂度是指数级的，所以不存在多项式时间的确定性算法来解决它，属于NP类问题。

（二）哈密尔顿回路问题

对于一个有向图，判断是否存在一条回路可以经过图中所有顶点且不重复的问题，称为哈密尔顿回路问题。
在遍历图中的顶点时，需要经过所有可能的路径从而判断，且需要遍历的路径呈指数级增加，所以该问题也是个NP类问题。

（三）判断回路问题

同样，对于一个图，若要判断图中是否有回路，可以通过深度优先搜索（DFS）和广度优先搜索（BFS）来判断，两种搜索算法都会遍及图中所有的结点，所以该问题也是个NP类问题。

（四）图的着色问题

给定一个无向图和若干种颜色，给图中的每个顶点着色，使得任意相邻的两个顶点颜色不同，即为图的着色问题。
若针对一个顶点涂色，则其邻边的顶点与该顶点颜色均不同，从而一直进行下去，该图中所有的颜色组合数呈指数级增加，可以采用贪心算法和回溯算法来解决，所以该问题也是个NP类问题。

（五）背包问题

给定一组物品，每个物品都有自己的重量和价值，背包的容量有限，求如何选择物品放入背包，使得背包内的物品总价值最大，即为背包问题。
同样，物品的选择和组合方式的数量随着物品数量的增加而呈指数级增长，所以该问题也是个NP类问题。

三、P类问题和NP类问题的区别

P类问题和NP类问题的区别在于时间复杂度，P类问题可以在多项式时间内的确定性算法来进行判定或求解问题，且一般P类问题的求解较简单，时间复杂度较低，而NP类问题可以在多项式时间内的不确定性算法来进行判定或求解问题，其求解过程较困难，但一般都是去验证问题。

四、NP完全问题

NP完全问题是NP问题的一个子类，可以说它是更复杂的问题，也是在多项式时间内验证问题的解。例如多项式变换技术问题、布尔可满足性问题以及上面的旅行商问题（TSP）、哈密尔顿回路问题等等。