我假设您正在寻找直观的定义，因为技术定义需要相当长的时间来理解。首先，让我们记住理解这些定义所需的初步概念。

• 决策问题 ：回答 是 或 否 的问题。

现在，让我们定义那些 复杂性类 。

磷

P 是一个复杂性类，表示可以在多项式时间内解决的所有决策问题的集合 。

也就是说，给定一个问题的实例，答案是或否可以在多项式时间内确定。

例子

给定一个连通图G，它的顶点可以用两种颜色着色，这样没有边是单色的吗？

算法：从任意顶点开始，将其着色为红色并将其所有邻居着色为蓝色并继续。当您用完顶点或被迫使边的两个端点都具有相同颜色时停止。

NP

NP 是一个复杂性类，表示所有决策问题的集合，其中答案为“是”的实例具有可以在多项式时间内验证的证明。

这意味着如果有人给我们一个问题的实例和一个证明（有时称为见证人）的答案是肯定的，我们可以在多项式时间内检查它是否正确。

例子

整数因式分解 在 NP 中。这是给定整数n和的问题m，是否有一个整数f与1 < f < m，这样f除n（f是
的一个小因数n）？

这是一个决策问题，因为答案是肯定或否定。如果有人递给我们一个问题实例（所以他们递给我们整数n和m）和一个f带有的整数1 < f < m，并声称这f是（证书）的一个因子，我们可以通过执行除法来检查 多项式时间内n的答案。 __n / f

NP-完全

NP-Complete 是一个复杂性类，它表示XNP 中所有问题的集合，可以将任何其他 NP 问题减少Y到X多项式时间内。

直观地说，这意味着Y如果我们知道如何快速解决，我们就可以快速解决X。准确地说，如果存在一个多项式时间算法将的实例转换为多项式时间内的实例，Y则可以简化为，并且当且仅当答案为是时，其答案为是。X``f``y``Y``x = f(y)``X``y``f(y)

例子

3-SAT. 这是一个问题，其中我们给出了 3 子句析取 (OR) 的合取 (AND)，形式为

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

其中每个x_vij都是布尔变量或来自有限预定义列表的变量的否定(x_1, x_2, ... x_n)。

可以证明， 每个 NP 问题都可以简化为 3-SAT 。这一点的证明是技术性的，需要使用 NP 的技术定义（ 基于非确定性图灵机 ）。这被称为
库克定理 。

使 NP 完全问题变得重要的是，如果可以找到确定性多项式时间算法来解决其中一个问题，那么每个 NP 问题都可以在多项式时间内解决（一个问题来统治所有问题）。

NP难

直观地说，这些问题 至少与 NP 完全问题一样难 。请注意，NP-hard 问题 不必在 NP 中， 也不必是决策问题 。

这里的精确定义是 一个问题X是 NP 难的，如果存在一个 NP 完全问题Y，那么它可以在多项式时间内Y归约到X。

但是由于任何 NP 完全问题都可以在多项式时间内归约为任何其他 NP 完全问题，因此所有 NP 完全问题都可以在多项式时间内归约为任何 NP
难题。那么，如果在多项式时间内有一个 NP-hard 问题的解决方案，那么在多项式时间内就有所有 NP 问题的解决方案。

例子

停机问题是一个NP-hard
问题。这是给定程序P和输入的问题，I它会停止吗？这是一个决策问题，但它不在 NP 中。很明显，任何 NP
完全问题都可以简化为这个问题。再举一个例子，任何 NP 完全问题都是 NP 难的。

我最喜欢的 NP 完全问题是扫雷问题。

P = NP

这是计算机科学中最著名的问题，也是数学科学中最重要的突出问题之一。事实上，克莱研究所提供一百万美元来解决这个问题（斯蒂芬库克在克莱网站上的文章非常好）。

很明显，P 是 NP 的子集。悬而未决的问题是 NP 问题是否具有确定性多项式时间解。人们普遍认为他们没有。这是最近一篇关于 P = NP
问题的最新（和重要性）的杰出文章：P 与 NP
问题的状态。