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

StackOverflow https://stackoverflow.com/questions/1857244

题

两者有什么区别 NP, NP完全 和 NP-硬?

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

有帮助吗？

解决方案

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

  • 决策问题:一个问题 是的 或者 不 回答。

现在，让我们定义那些 复杂度等级.

磷

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 是一个复杂性类别，代表所有问题的集合 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 是一个布尔变量或来自有限预定义列表的变量的否定 (x_1, x_2, ... x_n).

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

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

NP难

直观上看，这些问题都是 至少与 NP 完全问题一样难. 。注意 NP 困难问题 不必在 NP 中, ， 和 它们不一定是决策问题.

这里的精确定义是 一个问题 X 是 NP 困难的，如果存在 NP 完全问题 Y, ，使得 Y 可以简化为 X 在多项式时间内.

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

例子

这 停止问题 是一个NP难问题。这是给定程序的问题 P 并输入 I, ，会停止吗？这是一个决策问题，但不属于 NP 问题。显然，任何 NP 完全问题都可以简化为这一问题。另一个例子，任何 NP 完全问题都是 NP 困难问题。

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

P = NP

这是计算机科学中最著名的问题，也是数学科学中最重要的悬而未决的问题之一。事实上， 克莱研究所 提供一百万美元来解决这个问题（斯蒂芬·库克的 写上去 Clay 网站上的内容相当不错）。

显然P是NP的子集。悬而未决的问题是 NP 问题是否具有确定性多项式时间解。人们普遍认为事实并非如此。这是最近一篇关于 P = NP 问题的最新（及其重要性）的优秀文章： P 与 NP 问题的现状.

关于这个主题的最好的书是 计算机与难处理性 由加里和约翰逊撰写。

其他提示

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

请注意难度如何从上到下增加：任何 NP 可以简化为 NP 完全, ，以及任何 NP-Complete 可以简化为 NP-Hard, ，全部在 P（多项式）时间内。

如果你能在 P 时间内解决一类更困难的问题，那就意味着你找到了如何在 P 时间内解决所有更简单的问题（例如，证明 P = NP，如果你弄清楚如何在 P 时间内解决任何 NP 完全问题） P时间）。

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

注意事项 Yes 或者 No 条目：

  • * 一个NP问题同时也是P，可以在P时间内解决。
  • ** NP-Hard 问题同时也是 NP-Complete，可以在 P 时间内验证。
  • *** NP 完全问题（所有这些问题构成 NP 困难的子集）可能是。其余的NP困难则不然。

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

这是一个非常正规的答案问的问题。

3233可以被写为两个其他数的乘积大于1？有没有什么办法来转转所有哥尼斯堡的七桥的路径，而不采取任何桥梁两次？这些都是共享一个共同的特点问题的例子。它可能不是很明显如何有效地确定的答案，但如果答案是“是”，然后有一个短期和快速检查证明。在第一种情况下51一个非平凡因式分解;在第二，行走桥（嵌合的约束）。路线

一个的决策问题是与是问题或没有答案，只有在一个参数变化的集合。说的问题COMPOSITE = { “是n复合材料”：n是整数}或EULERPATH = { “是否图表G具有欧拉路径？”：G是有限图形}。

现在，一些决策问题借给自己有效的，如果不是明显的算法。欧拉发现了像“柯尼斯堡七桥问题”的问题超过250年前的高效算法。

在另一方面，对于许多决策问题，这不是明显的如何得到答案 - 但如果你知道的信息，一些额外的一块，很明显如何去证明你有正确的答案。复合材料是这样的：审判庭是明显的算法，它是缓慢：以因子10位数字，你必须尝试像100000个可能除数。但是，如果，例如，有人告诉你，61是3233除数，简单长除法是看他们是正确的一个有效方式。

在复杂类的 NP 与类的决策问题，其中“是”的答案有短状态，快速检查证明。比如复合。其中重要的一点是，这个定义并没有说这个问题有多难事情。如果你要解决一个决策问题正确的，有效的方式，只是在解决方案写下的步骤是足以证明。

算法研究的继续，并且新聪明算法创建的所有的时间。你可能不知道的问题如何解决有效今天可能会变成有效率的（如果不是明显）明天的解决方案。事实上，研究人员花费了直到 2002 找到一个有效的解决方案组合！有了这些进步，人们真的要怀疑：这是一些关于有短证明只是一种假象？也许的每一个的决定，即适合于高效的证据问题有一个有效的解决方案？ 没人知道。

也许这个领域最大的贡献来自与发现一个奇特的类的NP问题。通过与电路模型玩弄用于计算，斯蒂芬·库克发现的NP品种，这是可证明为硬或比的每一个的其他NP问题更难决策问题。对于布尔可满足性问题的有效解决方案可以用来创建一个有效的溶液至任何其他在NP问题。不久之后，理查德·卡普表明，其他一些决策问题可以起到相同的作用。这些问题，在某种意义上在NP “重” 的问题，成为被称为的 NP完全问题。

当然，NP是只有一类的决策问题。许多问题不是自然地用这种方式说：“找到N的因素”，“发现在访问每个顶点的图G的最短路径”，“给一组变量赋值，使下面的布尔表达式真”。虽然人们可以非正式TALK的一些这样的问题是“在NP”，在技术上，它没有多大意义 - 它们不是决策问题。其中有些问题甚至可能具有相同的排序功率为NP完全问题的：一个有效的解决方案，以这些（非决定）问题，将直接导致有效解决任何NP问题。像这样的问题被称为的 NP-硬

除了其他伟大的答案，这里是典型模式人使用，以显示NP，NP完全，和NP-硬的区别是：

“在这里输入的图像描述”

P（多项式时间）：作为名称本身所暗示的，这些是可以在多项式时间内解决的问题

。

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

NP-硬：这些是至少硬如在NP最难问题。如果我们能够解决在多项式时间内这些问题，我们可以解决任何NP问题都不可能存在。请注意，这些问题不一定是NP问题。这意味着，我们可以/-无法验证该溶液在多项式时间内这些问题。

NP完全：这些是它们都是NP和NP-硬的问题。这意味着，如果我们能够解决这些问题，就可以解决任何NP其他问题，并且这些问题的解决可在多项式时间进行验证。

解释P诉NP和例如没有进入技术性是比较“字问题”与“多选择问题”的最简单方法。

当你试图解决一个“字问题，”你必须要找到从零开始的解决方案。 当你试图解决一个“多选问题”你有一个选择：要么解决它，你会一“字问题”，或尝试在每个给你的答案的堵塞，并选择适合的候选答案。

经常出现这样一种“多选问题”比相应的“应用题”要容易得多：替代候选答案，并检查它们是否可能需要显著较少的努力不是从头开始寻找合适的答案

现在，如果我们同意，需要多项式时间的努力“易”，那么P级将包括“容易题”，和NP类将包括“易多重选择的问题。”

。

点v NP的本质是这样的问题：“有没有什么简单的选择题的问题，是不容易，因为这个词的问题”？也就是说，是否有这很容易验证给定答案的有效性问题，但发现从头这个问题的答案是困难的？

现在我们已经了解了NP直观的东西，我们要挑战我们的直觉。事实证明，有“多选问题”，在某种意义上说，是最难的所有的人都：如果一个人会找到的那些“最困难的他们全部的”问题一个一个解决人们将能够找到一个解决所有NP问题！当库克在40年前发现了这一点，就作为一个完整的惊喜。这些“最难他们的所有”问题被称为NP困难。如果你发现一个“字问题解决”其中之一，你会自动找到一个“字问题解决方案”，每一个“容易的多选问题”！

最后，NP完全问题的是那些同时NP和NP难题。根据我们的比喻，他们同时是“容易的多选问题”和“最难他们全部为题”。

有这个特殊问题真的很好的答案，所以没有写点我自己的解释。所以我会尝试与有关不同类别的计算复杂性一个很好的资源做出贡献。

有关的人谁认为计算复杂度大约只有P与NP，这里大约是不同的计算复杂性问题的最详尽的资源 。除了由OP问的问题，它列出大约500个不同类别的漂亮的描述也基本研究论文，它们描述类列表中的计算问题。

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

  1. 在NP中
  2. np-硬

enter image description here

- 介绍。算法 (3ed)，作者：Cormen、Leiserson、Rivest 和 Stein，第 1069 页

发现一些有趣的确定指标：

“在这里输入的图像描述”

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top