简介

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

P 问题

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

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

1. 对于所有的输出，M 都会在多项式工夫内运行
2. 对于 L 中所有的 x, M 的输入都是 1
3. 对于不在 L 中的所有 x，M 输入都是 0

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

NP 问题

在计算复杂度实践中，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 中依然存在许多问题，这些问题如同无奈在多项式工夫内失去解决。对于这些问题在多项式工夫内是否可能被解决是计算机科学中最大的未解决问题之一。

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

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

NPC 问题

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

1. 一个不确定的图灵机能够在多项式工夫内求解。
2. 确定性的 Turing 机能够在较大的工夫复杂度中进行求解（EXPTIME 或者暴力搜索算法），并且能够在多项式工夫内验证其解。
3. 它能够用来模仿任何其余具备类似可解性的问题（NP 中的其余问题都能够在多项式工夫内转换或者规约为该问题）。

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

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

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

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

NP-hard

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

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

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

P 和 NP 问题

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

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

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

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

本文已收录于 http://www.flydean.com/04-p-np-npc-problem/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！