首页 文章

NP，NP-Complete和NP-Hard有什么区别？

提问于
浏览 次
966

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

我知道网上有很多资源 . 我想阅读你的解释，原因是它们可能与那里有什么不同，或者它在那里，我不知道 .

algorithm complexity-theory computer-science np-complete np-hard

10 回答

  • 16

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

    • Decision problem ： yes 或 no 答案存在问题 .

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

    P.

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

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

    Example

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

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

    NP

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

    这意味着如果有人向我们提供了问题的实例和证书（有时称为证人），答案是肯定的，我们可以检查它在多项式时间内是否正确 .

    Example

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

    这是一个决策问题，因为答案是肯定或否定 . 如果有人向我们提出问题的实例（因此他们将整数 n 和 m ）和 f 整数 f 交给我们，并声称 f 是 n （证书）的一个因子，我们可以通过执行来检查多项式时间的答案分裂 n / f .

    NP-Complete

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

    直观地说，这意味着如果我们知道如何快速解决 X ，我们可以快速解决 Y . 确切地说， Y 可以简化为 X ，如果有一个多项式时间算法 f 将 Y 的 Y 实例 x = f(y) 转换为多项式时间的 x = f(y) ， y 的答案属性为yes，当且仅当答案为 f(y) 时是是的 .

    Example

    3-SAT . 这是我们给出3个子句析取（OR）的结合（ANDs），形式的陈述的问题

    (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-hard

    直觉上，这些问题至少与NP完全问题一样困难 . 请注意，NP难题不必在NP中，并且它们不一定是决策问题 .

    这里的精确定义是，如果存在NP完全问题 Y ，则问题 X 是NP难的，这样 Y 在多项式时间内可简化为 X .

    但由于任何NP完全问题可以在多项式时间内减少到任何其他NP完全问题，所以所有NP完全问题可以在多项式时间内减少到任何NP难问题 . 然后，如果在多项式时间内存在一个NP难问题的解，则在多项式时间内存在所有NP问题的解 .

    Example

    停止问题是NP难问题 . 这是给出一个程序 P 并输入 I 的问题，它会停止吗？这是一个决策问题，但它不在NP中 . 很明显，任何NP完全问题都可以简化为这个问题 . 作为另一个例子，任何NP完全问题都是NP难的 .

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

    P = NP

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

    它的明确P是NP的子集 . 开放性问题是NP问题是否具有确定性多项式时间解 . 人们普遍认为他们没有 . 这是一篇关于P = NP问题的最新（和重要性）的最新文章：The Status of the P versus NP problem .

    关于这个主题的最好的书是由Garey和Johnson撰写的Computers and Intractability .

    回复于
  • 5

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

    注意难度从上到下增加：任何NP都可以减少到NP-Complete，任何NP-Complete都可以减少到NP-Hard，全部在P（多项式）时间内 .

    如果你能在P时间内解决一类更难的问题，那就意味着你找到了如何在P时间内解决所有更容易的问题（例如，证明P = NP，如果你弄清楚如何解决任何NP-Complete问题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 条目的注释：

    • *也是P的NP问题在P时间内是可解的 .

    • **也是NP-Complete的NP-Hard问题在P时间内是可验证的 .

    • *** NP-完全问题（所有这些都是NP-hard的子集）可能是 . NP的其余部分很难 .

    我还发现this diagram非常有用，可以看到所有这些类型如何相互对应（更多地关注图的左半部分） .

    回复于
  • 73

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

    3233可以写成另外两个大于1的数字的乘积吗？有没有办法绕过所有的Seven Bridges of Königsberg而不需要两次桥接？这些是具有共同特征的问题的示例 . 如何有效地确定答案可能并不明显，但如果答案是'yes'，那么有一个简短快速的检查证据 . 在第一种情况下，51的非平凡因子分解;在第二个，一个走桥梁的路线（适应约束） .

    decision problem 是具有是或否答案的问题集合，仅在一个参数中有所不同 . 说问题COMPOSITE = {“是 n composite”： n 是一个整数}或EULERPATH = {“图 G 是否有欧拉路径？”：_ G 是有限图} .

    现在，一些决策问题有助于提高效率，即使不是很明显的算法 . 欧拉在250多年前发现了一种有效的算法来解决诸如“柯尼斯堡的七桥”之类的问题 .

    另一方面，对于许多决策问题，如何得到答案并不明显 - 但如果你知道一些额外的信息，很明显如何证明你已经得到了正确答案 . COMPOSITE是这样的：试验除法是明显的算法，而且它很慢：要算出一个10位数的数字，你必须尝试类似100,000个可能的除数 . 但是，例如，如果某人告诉你61是3233的除数，那么简单的长除法是一种有效的方法，可以看出它们是正确的 .

    复杂性类 NP 是决策问题的类别，其中'yes'答案具有简短状态，快速检查校样 . 像COMPOSITE一样 . 一个重要的一点是，这个定义并没有说明问题的严重程度 . 如果您有一个正确，有效的方法来解决决策问题，那么只需写下解决方案中的步骤就足够了 .

    算法研究仍在继续，并且一直在创建新的聪明算法 . 你今天可能不知道如何有效解决的问题可能会在明天有一个有效的（如果不是很明显的）解决方案 . 事实上，研究人员直到2002才找到了有效的COMPOSITE解决方案！随着所有这些进步，人们真的不得不怀疑：这有点短暂的证据只是一种幻觉吗？也许每个有助于高效证明的决策问题都有一个有效的解决方案？ Nobody knows .

    也许对这一领域的最大贡献来自于发现一种特殊的NP问题 . 通过利用电路模型进行计算，斯蒂芬库克发现了NP品种的决策问题，这个问题可能比其他NP问题更难或更难 . 可以使用boolean satisfiability problem的有效解决方案为NP中的任何其他问题创建有效的解决方案 . 不久之后，理查德卡普表明，其他一些决策问题可以达到同样的目的 . 从某种意义上说，NP中的这些问题被称为 NP-complete 问题 .

    当然，NP只是一类决策问题 . 许多问题都没有多大意义 - 它们不是决策问题 . 其中一些问题甚至可能与NP完全问题具有相同的权力：这些（非决策）问题的有效解决方案将直接导致任何NP问题的有效解决方案 . 像这样的问题被称为 NP-hard .

    回复于
  • 16

    除了其他伟大的答案，这里是typical schema用于显示NP，NP-Complete和NP-Hard之间的区别：

    enter image description here

    回复于
  • 41

    解释P v.NP等最简单的方法是进行技术性比较“词汇问题”与“多项选择题” .

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

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

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

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

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

    最后，NP完全问题是那些同时NP和NP难的问题 . 按照我们的比喻，它们同时“容易作为多项选择问题”和“其中最难解决的是单词问题” .

    回复于
  • 3

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

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

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

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

    回复于
  • 217

    NP完全问题是NP-Hard和复杂度NP中的问题 . 因此，为了表明任何给定的问题是NP完全的，你需要证明问题是在NP中并且它是NP难的 .

    NP复杂度类中的问题可以在多项式时间中非确定性地求解，并且可以针对多项式时间中的问题验证NP中的问题的可能解（即证书） .

    k-clique问题的非确定性解决方案的一个例子是：

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

    2）验证这些k个节点形成一个集团 .

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

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

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

    回复于
  • 51

    我想我们可以更简洁地回答这个问题 . 我回答了一个related question，并从那里复制了我的答案

    但首先，NP难问题是一个我们无法证明存在多项式时间解的问题 . 一些“问题-P”的NP-硬度通常通过将已经证实的NP难问题转换为多项式时间中的“问题-P”来证明 .

    要回答其余问题，首先需要了解哪些NP难题也是NP完全的 . 如果NP难问题属于集合NP，则它是NP完全的 . 要属于集合NP，问题需要是（i）决策问题，（ii）问题的解决方案的数量应该是有限的，并且每个解决方案应该是多项式长度，并且（iii）给定多项式长度解，我们应该能够说出问题的答案是肯定还是否现在，很容易看出可能存在许多不属于集合的NP难题NP并且更难解决 . 作为一个直观的例子，我们需要找到实际时间表的旅行推销员的优化版本比旅行推销员的决策版本更难，我们只需要确定长度<= k的时间表是否存在 .

    回复于
  • 39

    这个特定的问题有很好的答案，所以没有必要写出我自己的解释 . 因此，我将尝试为不同类别的计算复杂性提供优质资源 .

    对于那些认为计算复杂度仅与P和NP有关的人，here is the most exhaustive resource关于不同的计算复杂性问题 . 除了OP提出的问题之外，它还列出了大约500种不同类型的计算问题，其中包含了很好的描述，还列出了描述该类的基础研究论文 .

    回复于
  • 1242

    据我了解，np-hard问题不是一个完全问题的问题 . 实际上，根据定义，每个np完全问题是：

    在NP中

    • np-hard
    • 简介 . Cormen，Leiserson，Rivest和Stein的算法（3ed），第1069页
    回复于

相关问题