1279

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

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

4

11 回答 11

1646

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

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

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

磷

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则可以简化为，并且当且仅当答案为是时，其答案为是。XfyYx = f(y)Xyf(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 问题的状态。

这方面最好的书是Garey 和 Johnson 的Computers and Intractability。

于 2009-12-07T01:46:59.497 回答
306

我一直在环顾四周，看到许多冗长的解释。这是一个小图表，可能有助于总结：

请注意难度是如何从上到下增加的：任何NP 都可以简化为 NP-Complete，并且任何NP-Complete 都可以简化为 NP-Hard，所有这些都在 P（多项式）时间内完成。

如果你能在 P 时间内解决更难的一类问题，这意味着你找到了如何在 P 时间内解决所有更简单的问题（例如，证明 P = NP，如果你在P 时间）。

____________________________________________________________
| 问题类型 | P时间可验证| P时间可解| 增加难度
_____________________________________________________________________| |
| 磷 | 是 | 是 | |
| NP | 是 | 是或否 * | |
| NP-完全 | 是 | 未知 | |
| NP-硬 | 是或否 ** | 未知*** | |
____________________________________________________________ V

注释Yes或No条目：

  • * 一个也是 P 的 NP 问题可以在 P 时间内解决。
  • ** 一个 NP-Hard 问题也是 NP-Complete 可以在 P 时间内验证。
  • *** NP-Complete 问题（所有这些都是 NP-hard 的一个子集）可能是。其余的 NP 硬不是。

我还发现这张图对于查看所有这些类型如何相互对应非常有用（请多注意图的左半部分）。

于 2013-10-22T06:08:02.787 回答
106

P（多项式时间）：顾名思义，这些都是可以在多项式时间内解决的问题。

NP（非确定性多项式时间）：这些是可以在多项式时间内验证的决策问题。这意味着，如果我声称某个特定问题存在多项式时间解，您要求我证明这一点。然后，我会给你一个证明，你可以在多项式时间内轻松验证。这类问题称为 NP 问题。请注意，这里我们不是在讨论这个问题是否存在多项式时间解。但我们谈论的是在多项式时间内验证给定问题的解决方案。

NP-Hard： 这些至少与 NP 中最难的问题一样难。如果我们能在多项式时间内解决这些问题，我们就可以解决任何可能存在的 NP 问题。请注意，这些问题不一定是 NP 问题。这意味着，我们可能/可能不会在多项式时间内验证这些问题的解决方案。

NP-Complete：这些是 NP 和 NP-Hard 的问题。这意味着，如果我们能够解决这些问题，我们就可以解决任何其他 NP 问题，并且这些问题的解决方案可以在多项式时间内得到验证。

于 2013-10-04T03:50:08.617 回答
79

这是对所提问题的非常非正式的回答。

3233 可以写成其他两个大于 1 的数字的乘积吗？有没有什么方法可以绕着柯尼斯堡的七座桥走一遍，而不需要走两次桥？这些是具有共同特征的问题示例。如何有效地确定答案可能并不明显，但如果答案是“是”，那么就有一个简短而快速的检查证明。在第一种情况下，61 的非平凡因式分解（53 是另一个素数）；第二，一条走桥的路线（符合约束条件）。

决策问题是一组问题的集合，答案是或否，仅在一个参数上有所不同。说问题 COMPOSITE={"Is nComposite": nis an integer} 或 EULERPATH={"Does the graph has Gan Euler path?": Gis anfinite graph}。

现在，一些决策问题适用于高效的算法，即使不是显而易见的算法。欧拉在 250 多年前发现了一种有效的算法来解决像“柯尼斯堡七桥”这样的问题。

另一方面，对于许多决策问题，如何得到答案并不明显——但如果你知道一些额外的信息，那么如何去证明你的答案是正确的就很明显了。COMPOSITE 是这样的：试除法是显而易见的算法，而且它很慢：要分解一个 10 位数字，您必须尝试大约 100,000 个可能的除数。但是，例如，如果有人告诉你 61 是 3233 的除数，那么简单的长除法是一种有效的方法来判断它们是否正确。

复杂性类别NP是一类决策问题，其中“是”的答案很简短，可以快速检查证明。像复合材料。重要的一点是，这个定义并没有说明问题的难度。如果你有一个正确、有效的方法来解决决策问题，只需写下解决方案中的步骤就足够了。

算法研究仍在继续，新的聪明算法一直在创造。您今天可能不知道如何有效解决的问题明天可能会变成有效（如果不明显）的解决方案。事实上，直到2002 年，研究人员才找到复合材料的有效解决方案！随着所有这些进步，人们真的不得不怀疑：这是否只是一种幻觉？也许每个适合于有效证明的决策问题都有一个有效的解决方案？ 没人知道。

也许对这一领域的最大贡献是发现了一类特殊的 NP 问题。通过使用用于计算的电路模型，斯蒂芬库克发现了一个 NP 类型的决策问题，可以证明它比其他任何 NP 问题都难或难。布尔可满足性问题的有效解决方案可用于为NP中的任何其他问题创建有效解决方案。不久之后，理查德·卡普展示了许多其他决策问题也可以达到同样的目的。这些问题，在某种意义上是 NP 中“最难”的问题，被称为NP 完全问题。

当然，NP 只是一类决策问题。许多问题不是自然地以这种方式陈述的：“找到 N 的因数”、“找到图 G 中访问每个顶点的最短路径”、“给出一组变量赋值，使以下布尔表达式为真”。尽管人们可能会非正式地谈论“在 NP 中”存在的一些此类问题，但从技术上讲，这并没有多大意义——它们不是决策问题。其中一些问题甚至可能具有与 NP 完全问题相同的能力：对这些（非决策）问题的有效解决方案将直接导致对任何 NP 问题的有效解决方案。像这样的问题称为NP-hard。

于 2009-12-07T02:42:44.397 回答
72

除了其他很好的答案之外，这里是人们用来显示 NP、NP-Complete 和 NP-Hard 之间区别的典型模式：

在此处输入图像描述

于 2014-11-24T17:50:15.480 回答
53

在不涉及技术细节的情况下解释 P v. NP 等的最简单方法是将“单词问题”与“多项选择问题”进行比较。

当您尝试解决“文字问题”时，您必须从头开始找到解决方案。当您尝试解决“多项选择问题”时，您有一个选择：要么像解决“单词问题”一样解决它，要么尝试插入给您的每个答案，然后选择合适的候选答案。

通常情况下，“多项选择题”比相应的“单词问题”要容易得多：替换候选答案并检查它们是否合适可能比从头开始寻找正确答案所需的努力要少得多。

现在，如果我们同意花费多项式时间“简单”的努力，那么 P 类将由“简单的单词问题”组成，而 NP 类将由“简单的多项选择问题”组成。

P v. NP 的本质是一个问题：“有没有像单词问题那样简单的多项选择题”？也就是说，是否存在容易验证给定答案的有效性但很难从头开始找到答案的问题？

既然我们直观地理解了 NP 是什么，我们就必须挑战我们的直觉。事实证明，存在“多项选择问题”，从某种意义上说，它们是所有问题中最难的：如果一个人能找到解决这些“最难”问题之一的方法，那么他就能找到所有问题的解决方案。 NP问题！当库克在 40 年前发现这一点时，完全出乎意料。这些“最难的”问题被称为 NP-hard。如果您找到其中一个的“文字问题解决方案”，您将自动为每个“简单的多项选择问题”找到一个“文字问题解决方案”！

最后，NP-complete 问题是那些同时是 NP 和 NP-hard 的问题。按照我们的类比，它们同时是“简单的选择题”和“最难的都是单词问题”。

于 2013-08-08T20:41:19.540 回答
19

我想我们可以更简洁地回答它。我回答了一个相关的问题，并从那里复制了我的答案

但首先，NP-hard 问题是我们无法证明多项式时间解存在的问题。一些“问题-P”的 NP-hardness 通常通过在多项式时间内将已经证明的 NP-hard 问题转换为“problem-P”来证明。

要回答剩下的问题，您首先需要了解哪些 NP-hard 问题也是 NP-complete。如果一个 NP-hard 问题属于集合 NP，那么它是 NP-complete。要属于集合 NP，需要有一个问题

(i) 一个决策问题，
(ii) 问题的解决方案的数量应该是有限的，并且每个解决方案都应该是多项式长度，以及
(iii) 给定一个多项式长度的解决方案，我们应该能够说出问题的答案是否问题是/否

现在，很容易看出可能存在许多不属于集合 NP 且更难解决的 NP 难题。作为一个直观的例子，我们需要找到实际时间表的旅行商的优化版本比我们只需要确定长度 <= k 的时间表是否存在的旅行商的决策版本更难。

于 2011-06-18T16:52:47.643 回答
18

NP 完全问题是既属于 NP-Hard 又属于复杂性类别 NP 的问题。因此，要证明任何给定问题都是 NP 完全的，您需要证明该问题既属于 NP 问题，又属于 NP 难题。

NP 复杂性类中的问题可以在多项式时间内以非确定性方式解决，并且可以在多项式时间内验证 NP 中问题的可能解决方案（即证书）的正确性。

k-clique 问题的非确定性解决方案的示例如下：

1) 从图中随机选择 k 个节点

2) 验证这 k 个节点是否形成了一个 clique。

上述策略在输入图的大小上是多项式的，因此 k-clique 问题在 NP 中。

请注意，在多项式时间内确定性可解决的所有问题也在 NP 中。

表明一个问题是 NP-hard 通常涉及使用多项式时间映射从其他一些 NP-hard 问题减少到您的问题：http://en.wikipedia.org/wiki/Reduction_(complexity)

于 2009-12-07T01:45:29.360 回答
5

这个特定问题有非常好的答案，所以没有必要写我自己的解释。因此，我将尝试提供有关不同类型计算复杂性的优秀资源。

对于认为计算复杂度仅与 P 和 NP 有关的人来说，这里是关于不同计算复杂度问题的最详尽的资源。除了 OP 提出的问题外，它还列出了大约 500 个不同类别的计算问题，并且描述得很好，还列出了描述该类别的基础研究论文。

于 2014-01-14T01:56:55.740 回答
4

找到一些有趣的定义：

在此处输入图像描述

于 2019-06-11T03:06:43.420 回答
1

据我了解，np-hard问题并不比np-complete问题“更难”。事实上，根据定义，每个 np-complete 问题都是：

  1. 在NP
  2. np 硬

在此处输入图像描述

- 介绍。由 Cormen、Leiserson、Rivest 和 Stein 撰写的算法 (3ed)，第 1069 页

条件 1. 和 2. 翻译成英文：

  1. 语言 L 在 NP 中，并且
  2. 每个 NP 语言都是多项式时间可约简为语言 L。
于 2014-08-13T13:57:11.690 回答