NP完全性理论
NP完全性理论
易解问题和难解问题
- 区别在于是否存在多项式时间算法
- 分类：P；NP；NPC；NPH
P类问题（Polynomial：多项式）
- 在确定性计算模型下的易解问题
- 存在多项式时间算法的问题
- P ∈ NP
NP类问题（Nondeterministic-Polynomial：非确定性多项式）
-
非确定性计算模型下的易验证问题
-
不知道是否存在多项式时间算法，但是可以在多项式时间内验证并得到此问题的一个正确解
-
（重点）例子：旅行家推销问题(TSP)。有一个推销员，到n个城市推销商品，要找出一个包含所有n个城市的环路，这个环路路径小于a。我们知道此问题如果单纯的用枚举法来列举的话会有(n-1)! 种，已经不是多项式时间的算法了(注：阶乘算法比多项式的复杂)。那怎么办呢？我们可以用猜的，假设我人品好，猜几次就猜中了一条小于长度a的路径，我画画画画，好的，我得到了一条路径小于a的环路，问题解决了。可是，我不可能每次都猜的那么准，也许我要猜完所有种才能得到结果。所以说，这是一个NP类问题。即我们能在多项式的时间内验证并得出问题的正确解，但却不知道该问题是否存在一个多项式时间的算法，每次都能解决它。 (注意，这里是不知道，不是不存在) 。
-
所以就产生了一个问题，NP=P ?，即是否 所有能在多项式时间内验证得出正确解的问题，都是具有多项式时间算法的问题呢。答案是有的存在，有的不存在。
-
为了证明这个千古难题，科学家想出了很多办法。其中之一就是问题的约化。所谓问题约化就是，可以用问题B的算法来解决A ，我们就说问题A可以约化成问题B。举个例子，一元一次方程的求解，跟二元一次方程的求解。我们知道，只要能求解二元一次方程，那就可以用二元一次方程的解法来求解一元一次方程，只需要将一元一次方程加上y，并附加一个方程y=0就可以将一元一次方程变形为一个二元一次方程，然后用二元一次方程的解法来求解这个方程。注意，这里二元一次方程的解法会比一元一次的复杂。所以我们说，只需要找到解二元一次方程的规则性解法，那就能用这个规则性解法来求解一元一次方程。从这里也可以看出，约化是具有传递性的，如A约化到B，B约化到C，A就可以约化到C，同时不断约化下去，我们会发现一个很惊人的特性，就是他一定会存在一个最大的问题，我们只需要解决了这个问题，那其下的所有问题也就解决了。这就是我们所说的NPC问题的概念。
-
引到NP问题里，对于同一类的所有的NP类问题，若他们都可以在多项式时间内约化成最难的一个NP类问题，（我们直观的认为，被约化成的问题应具有比前一个问题更复杂的时间复杂度）当我们针对这个时间复杂度最高的超级NP问题要是能找到他的多项式时间算法的话，那就等于变向的证明了其下的所有问题都是存在多项式算法的，即NP=P！！！
NPC（Nondeterministic-Polynomial-Complete：非确定性多项式完全）NP完全问题
- 一个问题满足
- 是NP问题
- 所有NP问题都可以约化成它，则称此问题为NPC问题
- NPC问题是NP问题的子集，即 NPC ∈ NP（是NP问题中最复杂的一个）
- 如果解决了NPC问题，那么所有NP问题都解决了，那么NP问题就存在多项式时间算法，可以推出 NP = P！！！
- 多数情况下NPC问题找不到多项式时间算法，更多的时候是一个指数级的算法
-
怎么证明一个问题是否是NPC问题
- 先证明是NP问题（P∈NP)
- 再证明其中一个NPC问题能约化到它
NPH（Nondeterministic-Polynomial-Hard）NP难问题
- 满足NPC定义的第二条但不一定满足第一条（即 NPH 比 NPC 更广）（所有NP问题都能约化成它，但它不一定是NP问题）