computer-science - NP、NP-Complete 和 NP-Hard 之间有什么区别？

Question

有什么区别NP , NP-完全和 NP-Hard ?

我知道网上有很多资源。我想阅读你的解释，原因是它们可能与外面的不同，或者有一些我不知道的东西。

Answer 1

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

决策问题 : 一个 的问题是 或 否 回答。

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

磷

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

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

示例

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

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

NP

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

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

示例

整数因式分解在 NP 中。这是给定整数 n 的问题和 m , 是否存在整数 f与 1 < f < m ，使得 f分 n ( f 是 n 的一个小因子)？

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

NP-完全

NP-Complete 是一个复杂度类，代表所有问题的集合 X在 NP 中可以减少任何其他 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是一个 bool 变量或来自有限预定义列表的变量的否定 (x_1, x_2, ... x_n) .

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

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

NP难

直觉上，这些问题至少与 NP 完全问题一样难。请注意，NP-hard 问题不一定是 NP，也不一定是决策问题。

这里的准确定义是问题 X是 NP-hard，如果存在 NP-完全问题 Y ，使得 Y可简化为 X在多项式时间内。

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

示例

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

我最喜欢的 NP 完全问题是 Minesweeper problem .

P = NP

这是计算机科学中最著名的问题，也是数学科学中最重要的突出问题之一。事实上， Clay Institute正在提供 100 万美元来解决这个问题(Clay 网站上斯蒂芬库克的 writeup 非常好)。

很明显，P 是 NP 的一个子集。悬而未决的问题是 NP 问题是否具有确定性多项式时间解。人们普遍认为他们没有。这是最近一篇关于 P = NP 问题的最新(和重要性)的杰出文章: The Status of the P versus NP problem .

关于该主题的最佳书籍是 Computers and Intractability加里和约翰逊。