13

我正在努力理解什么是非确定性多项式时间问题和 NP 完全问题。我了解多项式时间可解决的问题，并在维基百科中看到了关于 NP 问题。在阅读完这篇文章后，我试图思考一些示例问题。据我了解，无向中的深度优先搜索是 NP 完全的，因为如果图很大（引用一个是如果图形大小很小，则为多项式。）

谁能在不使用太多数学的情况下用简单的例子简要解释所有这些 NP 术语？

4

3 回答 3

42

关于NP和NP 完备性有很多思考方式。我将从NP的定义开始，然后讨论NP硬度，最后是NP完整性。

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

如果它是一个可以在多项式时间内验证正确答案的是或否问题（决策问题），则该问题属于NP 。例如，一个经典的NP问题是查看给定一组已知权重的权重，您是否可以选择一组权重恰好为某个量 k 的权重（这称为子集和问题）。确定是否存在具有该属性的一组权重可能很棘手，但如果我要给你一组我说我知道是正确的权重，你可以很容易地检查我是否给了你正确的一组权重，只需将它们相加并查看它们是否总计为 k。

NP被称为“非确定多项式”的原因是，考虑NP的另一种方式是考虑一种神奇的算法，该算法可以在多项式时间内以某种方式猜测问题的正确答案。也就是说，如果您可以编写一个允许对问题的答案进行猜测并在多项式时间内运行的算法，那么您要解决的问题就是NP. 回到我们的权重示例，我们可以为这个问题编写这样一个猜测算法，如下所示。首先，在线性时间内猜测哪一组权重是正确的一组权重，然后将它们全部加起来，看看它们的总和是否为 k。如果是，请报告答案为“是”。否则，说“不”。如果这个程序总是保证做出正确的猜测，那么给定任何有解决方案的问题的输入，它总是会找到一个并报告“是”，如果没有解决方案，它总是会猜错并报告“否”。

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

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

更正式地说，如果在多项式时间内，您可以将任何其他NP问题的任何实例转换为该问题的实例，则NP中的问题称为NP完全问题。上面的权重问题就是这样一个问题，确定布尔公式是否具有令人满意的分配，解决整数上的某些优化问题（整数规划），确定访问一组位置的最快路线（旅行商)，或确定如何使用最少的频率分配城市中的蜂窝塔（图形着色）。甚至确定是否可以解决像数独这样的游戏众所周知，扫雷艇对于任意棋盘尺寸都是NP 完备的。

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

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

至于您对 DFS 是NP 完全的最初想法，只有问题可以在NP中或是NP 完全的；算法不能。DFS 是一种解决图可达性问题的算法——给定图中的两个节点，是否有从第一个节点到第二个节点的路径？这个问题在NP中，因为如果有一条路径很容易检查，但它（可能）不是NP 完全的，因为我们知道我们可以使用 DFS 在多项式时间内解决它。

希望这可以帮助！

于 2011-08-02T18:03:38.357 回答
1

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

于 2011-08-02T17:49:14.930 回答
1

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

几个问题

  • DFS 不是 NP-Hard 问题，因此它不是 NP-complete。
  • NP-completeness 必须用决策问题来表述-我不知道您做出错误决策是什么意思
  • 输入的大小与 NP 完全性或硬度无关。每个问题都有一个运行时间作为问题大小的函数，该函数的大小是决定多时间的方式（即，如果它是多项式或指数的）
于 2011-08-02T17:50:50.980 回答