简介

咱们在做组合优化的时候须要去解决各种问题，依据问题的复杂度不同能够分为P、NP、NPC问题等。明天给大家来介绍一下这些问题类型。

P问题

在计算复杂度实践中，P（也称为PTIME或DTIME）是根本的复杂度类型。它是指可能应用确定图灵机在多项式工夫内解决的所有决策问题。

这里咱们给一下P的定义，如果一个公式语言L是一个P类型，那么当且仅当存在这样的一个确定图灵机M时成立：

常见的P问题包含线性规划的决策版本，计算最大公因数和找到最大匹配。在2002年，证实了确定数字是否为质数的问题也是一个P问题。

在计算复杂度实践中，NP（nondeterministic polynomial time）不确定性多项式工夫次要用来掂量分类决策问题的复杂度。 NP是一组决策问题，对于这些问题实例来说，如果答案为“是”，那么示意该实例应用确定图灵机可在多项式工夫内验证胜利。

NP实际上是由两个阶段组成的，第一阶段包含对解决方案的猜想，该阶段以非确定性形式生成，而第二阶段包含确定性算法，验证猜想是否能够解决问题。也就是说NP= nondeterministic + polynomial。

依据P和NP的定义，咱们能够发现所有的P问题都是NP问题，因为P的定义是所有问题都能够在多项式工夫内确定地解决，而NP的定义是问题能够在多项式工夫内失去验证的问题。

然而NP蕴含了更多的问题，其中NP中最难的问题被称为NP-complete 问题。解决多项式工夫中的此类问题的算法也可能解决多项式工夫中的任何其余NP问题。

在计算机科学中，很多搜寻优化的问题都能够被看做是NP问题。旅行商问题就是一个典型的NP问题。

“给出一个城市列表以及每对城市之间的间隔，要找到一条拜访每个城市一次最初返回原城市的最短门路” 这是组合优化中的一个NP难题，在实践计算机科学和运筹学中很重要。

因为NP问题中蕴含了很多理论生存中十分重要的问题，所以人们为查找NP中的多项式工夫算法付出了微小的致力。然而，NP中依然存在许多问题，这些问题如同无奈在多项式工夫内失去解决。对于这些问题在多项式工夫内是否可能被解决是计算机科学中最大的未解决问题之一。

在这种状况下，引入了一个重要的概念就是NP齐全决策问题集(NP-complete),它是NP的子集，能够非正式地形容为NP中“最难”的问题。如果咱们说一个问题被证实是NPC问题，那么意味着在这个问题上无奈找到多项式工夫算法。

然而，在理论利用中，通常不会破费大量的计算去寻找一个最优解，然而能够在多项式工夫内找到一个次优解，这对于理论利用就曾经足够了。

在计算复杂度实践中，满足以下状况的问题是NPC问题：

依据规定3，因为NPC问题是NP问题的更加简单的模式，如果你能够找到一个解决某个 NP-complete 问题的多项式算法，那么所有的 NP 问题都将能够很容易地解决。

举个例子，一个一元一次方程能够规约为求一个一元二次方程，只须要将二次型系数变为0即可。通过一直地规约，咱们能失去复杂度更高然而利用范畴更广的算法来代替复杂度虽低然而利用范畴小的一类问题的算法。

只管能够“疾速”验证NPC问题的解决方案，然而没有已知的办法能够疾速找到解决方案。即，随着问题的大小增长，应用任何以后已知的算法解决问题所需的工夫迅速减少。

仍未发现用于计算NP齐全问题的解决方案的办法，然而计算机科学家和程序员依然常常遇到NP齐全问题。 NP齐全问题通常通过应用启发式办法和近似算法来解决。

在计算复杂性实践中，NP-hard是对一类问题的形容，这些问题“至多与NP中最难的问题一样难”。 NP-hard问题的一个简略例子是子集和问题。

如果一个已知的NPC问题可能规约到此问题，那么这个问题就叫做NP-hard问题。

所以NPC问题肯定是NP-Hard问题，但并不是所有的NP-Hard问题都是NPC问题。

P和NP问题是计算机科学中尚未解决的次要问题。它议论的是如果一个问题能够疾速的被验证，那么该问题是否能够被疾速解决？

P是指该问题可能在多项式工夫内找到解决方案，而NP是指如果找到候选的答案，则可能进行疾速验证。

个别状况下大家都工作P ！= NP，也就是说尽管无奈在多项式工夫内解决，但答案能够在多项式工夫内验证。

依据P和NP是否雷同，咱们别离作出P、NP、NPC和NP-Hard的关系图。

本文已收录于 http://www.flydean.com/04-p-np-npc-problem/
最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！
欢送关注我的公众号:「程序那些事」,懂技术，更懂你！