简介

我们在做组合优化的时候需要去解决各种问题，根据问题的复杂度不同可以分为 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/

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

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