NP和NP-complete问题是什么？

Question

NP和NP-complete问题是什么？

13

我很难理解什么是非确定性多项式时间问题和NP完全问题。我了解什么是多项式时间可解问题，并在维基百科上看到了关于NP问题的介绍。阅读后，我尝试考虑一些示例问题。据我所知，对于无向图中的深度优先搜索而言，由于每个决策都可以被非确定地做出（即如果我做错了一个决定，我可以尝试一些其他选择），因此它是NP完全的，如果图很大，则可以是多项式的，如果图的大小很小。

有没有人能够用简单的例子简要解释所有这些NP术语，而不使用太多数学公式？

- Mr.Anubis

1

DFS肯定在P中，每个搜索也是如此。您可以使用队列，在O（n）时间内检查所有n个节点。 - Rag

@Brian Gordon：这使得它在节点数量上是线性的，但节点数量本身是指数级的。 - S.L. Barth

@S.L. Barth 指什么参数的指数函数？ - Rag

请阅读 http://stackoverflow.com/questions/how-to-ask。 - Robert Harvey

@Brian Gordon 从我的记忆中，这个指数与节点拥有的属性数量成正比。（我在这里称它们为属性，以避免与参数术语混淆）。 - S.L. Barth

3个回答

1

我在大学时学到了一个经验法则：如果给定一个解决方案，能够快速验证该解决方案（即在多项式时间内），那么问题就属于 NP 类问题。

- S.L. Barth

NP完全问题也必须是NP难问题。 - Rag

1

我将尝试解析您的示例，希望在网络上的所有其他资源的帮助下，您可以取得进展。

有几个问题

DFS不是NP-Hard问题，因此它不是NP-complete。
NP完备性必须用决策问题的术语来表述 - 我不知道您所说的错误决策是什么意思
输入的大小与NP完备性或难度无关。每个问题都有一个作为问题大小函数的运行时间，该函数的数量级是如何决定多项式时间的（即，如果它是多项式还是指数）

- dfb

NP难度是NP完备性的必要条件。 - dfb

抱歉，我读错了，把NP-complete误认为只是NP问题了。 - tskuzzy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

NP和NP-完全性有很多思考方式。我将从NP的定义开始，然后将谈论NP-难度，最后是NP-完全性。

在高层次上，P和NP是问题类别。如果一个问题是一个yes或no的问题（一个“decision problem”），并且有一些算法可以在多项式时间内解决该问题，则该问题属于P。例如，“你能否从节点u到节点v在这个图中？”的问题属于P，因为你可以通过深度优先搜索解决它。（请注意，DFS本身不在P中，因为DFS是一个算法而不是一个问题）。另一个P中问题的例子是检查一个序列是否按排序顺序排列。

如果一个问题是一个可以在多项式时间内验证正确答案的yes-or-no问题（即decision problem），那么它就属于NP。例如，一个经典的NP问题是看看是否可以在已知重量的一组重量中选择一组恰好重量为k的重量（这被称为subset sum problem）。确定具有该属性的重量集是否存在可能有些棘手，但是如果我给你一个我知道是正确的重量集，你可以通过将它们相加并查看它们是否总计为k来轻松检查我是否给出了正确的重量集。

NP之所以被称为“非确定性多项式”，是因为另一种思考NP的方式是想象一个神奇的算法，可以在多项式时间内猜出问题的正确答案。也就是说，如果你能编写一个允许猜测问题答案并在多项式时间内运行的算法，那么你解决的问题就属于NP。回到我们的重量例子，我们可以为该问题编写以下猜测算法。首先，在线性时间内猜测哪个重量集合是正确的，然后将它们全部加起来，看是否总和为k。如果是，则报告答案为“是”。否则，报告“否”。如果这个程序总是保证做出正确的猜测，那么对于任何有解的问题输入，它都会找到一个并报告“是”，如果没有解，则总是猜错并报告“否”。

计算机科学中最基本和重要的问题之一是，已知任何一个NP问题是否也属于P。也就是说，如果我们可以有效地（在多项式时间内）验证问题的答案，那么我们是否总能以多项式时间解决该问题？已知任何P问题也是NP问题，因为你可以使用多项式时间算法产生一个答案，然后检查它是否正确，但没有人找到一种在多项式时间内解决任意NP问题的方法。

这是因为一些NP问题被称为NP-complete，意味着（非正式地）它们至少与NP中的其他问题一样难。如果我们能够高效地（多项式时间）解决这些问题，那么我们就可以在多项式时间内解决NP中的每个问题。这将是一个巨大的进展，因为NP中有很多极为重要的问题，我们目前没有好的快速算法来解决。这也是P=NP问题的吸引力所在，因为只需要一个算法就可以表明一类被认为难以实际解决的问题实际上可以高效地解决。

更正式地说，如果在多项式时间内，您可以将任何其他 NP 问题的任何实例转换为该问题的实例，则称 NP 中的问题为 NP -complete。带权重的上述问题是这样一个问题，确定布尔公式是否具有满足的赋值，解决整数优化问题（整数规划），确定访问一组位置的最快路线（旅行商）或确定如何使用最少的频率在城市中分配基站（图形染色）也是如此。即使对于任意的棋盘大小，确定是否可能解决像数独和扫雷这样的游戏也被认为是 NP -complete。

（有些问题具有后一种属性-任何 NP 中的问题都可以有效地转换为该问题-但它们本身不属于 NP 。那些问题被称为 NP -hard。）

从实际角度来看，如果你被要求解决一个已知是NP完全问题或NP难问题，不要期望在合理的时间内找到精确解决方案。在某些情况下，甚至不能有效地近似解决方案。最好寻找其他问题尝试解决，或者接受启发式解决方案，在大多数情况下表现良好但并非所有情况都如此。

至于你对DFS是NP完全问题的原始想法，只有问题才能在NP中或是NP完全问题；算法则不能。DFS是用于解决图形可达性问题的算法——给定图中的两个节点，第一个节点是否可以到达第二个节点？该问题处于NP中，因为如果存在路径，则易于检查，但我们可以使用DFS在多项式时间内解决它，所以这个问题可能不是NP完全问题。

希望这可以帮助你！