22

假设您有一些数学背景，您将如何向天真者提供计算复杂性理论的一般概述？

我正在寻找 P = NP 问题的解释。什么是P？什么是NP？什么是 NP-Hard？

有时 Wikipedia 写得好像读者已经理解了所涉及的所有概念。

4

10 回答 10

61

呵呵，博士论文闪回。好的，这就去。

我们从决策问题的概念开始，一个算法总是可以回答“是”或“否”的问题。我们还需要两种计算机模型（实际上是图灵机）的想法：确定性和非确定性。确定性计算机是我们一直想到的常规计算机；非确定性计算机就像我们习惯的那样，只是它具有无限的并行性，因此每当您来到一个分支时，您都会产生一个新的“进程”并检查双方。就像 Yogi Berra 说的，当你走到岔路口时，你应该接受它。

如果存在已知的多项式时间算法来获得该答案，则决策问题在 P 中。如果存在用于非确定性机器的已知多项式时间算法来获得答案，则决策问题属于 NP。

已知存在于 P 中的问题在 NP 中是微不足道的——非确定性机器从不麻烦自己分叉另一个进程，并且就像确定性机器一样工作。有已知的问题既不在 P 也不在 NP 中；一个简单的例子是枚举所有长度为 n 的位向量。无论如何，这需要 2 n步。

（严格来说，如果一个节点确定性机器可以在多时间内得出答案，并且确定性机器可以在多时间内验证该解决方案是否正确，则决策问题属于 NP。）

但是有一些已知存在于 NP 中的问题，对于这些问题，没有已知的多时间确定性算法；换句话说，我们知道它们在 NP 中，但不知道它们是否在 P 中。传统的例子是旅行商问题（decision-TSP）的决策问题版本：给定城市和距离，有没有一条覆盖所有城市，返回起点，距离小于x的路线？在不确定的机器中很容易，因为每次不确定的旅行推销员走到岔路口时，他都会接受：他的克隆人前往下一个他们没有去过的城市，最后他们比较笔记，看看是否任何克隆的距离都小于x。

（然后，成倍增加的克隆人会为了哪些必须被杀死而与之抗争。）

不知道决策 TSP 是否在 P 中：没有已知的多时间解决方案，但没有证据表明这种解决方案不存在。

现在，还有一个概念：给定决策问题 P 和 Q，如果算法可以在多项式时间内将 P 的解转换为 Q 的解，则称 Q可多次约简（或仅可约简）为 P。

如果您可以证明 (1) 它在 NP 中，并且 (2) 表明它可以多次还原为已知为 NP 完全的问题，则该问题是 NP 完全的。（其中困难的部分是证明NP 完全问题的第一个例子：这是由史蒂夫库克在库克定理中完成的。）

真的，它说的是，如果有人找到了一个 NP 完全问题的多时间解决方案，他们就会自动为所有NP 完全问题找到一个解决方案；这也意味着P = NP。

一个问题是 NP 难的当且仅当它“至少”与一个 NP 完全问题一样难。寻找最短路线的更传统的旅行商问题是 NP 难的，而不是严格的 NP 完全问题。

于 2008-11-21T17:13:23.697 回答
5

Michael Sipser的《计算理论导论》是一本很棒的书，可读性很强。另一个很好的资源是 Scott Aaronson在理论计算机科学课程中的伟大想法。

所使用的形式主义是将决策问题（带有是/否答案的问题，例如“该图是否具有哈密顿循环”）视为“语言”——字符串集——答案为“是”的输入。关于“计算机”是什么（图灵机）有一个正式的概念，如果在图灵机上有一个多项式时间算法来决定该问题（给定输入字符串，比如是或否），那么问题就在 P 中。

如果它在多项式时间内是可检查的，则在 NP 中存在问题，即，如果对于答案为“是”的输入，有一个（多项式大小）证书，您可以在多项式时间内检查答案是否为“是”。[例如，给定一个哈密顿循环作为证书，您显然可以检查它是一个。]

它没有说明如何找到该证书。显然，您可以尝试“所有可能的证书”，但这可能需要成倍的时间；目前尚不清楚您是否总是需要花费超过多项式的时间来决定是或否；这是 P 与 NP 的问题。

如果能够解决该问题意味着能够解决 NP 中的所有问题，则该问题是 NP 难的。

另请参阅此问题： 什么是计算机科学中的 NP 完全？

但实际上，所有这些对你来说可能只是模糊的；值得花时间阅读例如 Sipser 的书。这是一个美丽的理论。

于 2008-11-21T16:04:11.717 回答
5

这是对查理帖子的评论。

如果您可以证明 (1) 它在 NP 中，并且 (2) 表明它可以多次还原为已知为 NP 完全的问题，则该问题是 NP 完全的。

第二个条件有一个微妙的错误。实际上，您需要证明的是已知的 NP 完全问题（例如Y）是多项式时间可简化为该问题（我们称其为问题X）。

这种证明方式背后的原因是，如果你可以将一个NP完全问题简化为这个问题，并设法在多时间内解决这个问题，那么你也成功地找到了NP的多时间解决方案-完整的问题，这将是一件了不起的事情（如果不是不可能的话），从那时起，您将成功解决长期存在的P = NP问题。

看待这个证明的另一种方法是将其视为使用反正证明技术，该技术基本上表明如果Y --> X，则~X --> ~Y。换句话说，不能在多项式时间内求解Y是不可能的，这意味着也不能在多项式时间内求解 X。另一方面，如果您可以在多时间内解决 X，那么您也可以在多时间内解决 Y。此外，您还可以通过传递性解决所有在多时间内减少到 Y 的问题。

我希望我上面的解释足够清楚。一个很好的来源是 Kleinberg 和 Tardos 的算法设计的第 8 章或 Cormen 等人的第 34 章。

于 2009-04-15T17:12:11.870 回答
4

不幸的是，我所知道的最好的两本书（Garey 和 Johnson以及Hopcroft 和 Ullman）都是从面向研究生证明的数学水平开始的。这几乎肯定是必要的，因为整个问题很容易被误解或错误描述。当Jeff试图以过于客气/开玩笑的语气来处理这件事时，他差点把耳朵咬断。

也许最好的方法是使用大量示例和练习，简单地使用大 O 表示法进行大量动手操作。另请参阅此答案。但是请注意，这并不完全相同：单个算法可以用渐近线来描述，但是说一个问题具有一定的复杂性是关于它的所有可能算法的陈述。这就是为什么证明如此复杂的原因！

于 2008-11-21T09:30:03.367 回答
2

我记得 Papadimitriou 的“计算复杂性”（我希望我的名字拼写正确）是一本好书

于 2008-11-21T10:49:26.670 回答
1

非常简化：如果解决问题的唯一方法是枚举所有可能的答案并检查每个答案，那么问题就是 NP 难的。

于 2008-11-21T11:58:31.133 回答
1

以下是有关该主题的一些链接：

在您熟悉集合基数的概念，即集合中元素的数量时，您可以将问题视为 P 表示整数的基数，而 NP 是一个谜：它是相同的还是更大的所有实数的基数？

于 2008-11-21T17:34:21.847 回答
0

我的简化答案是：“计算复杂性是对添加更多元素时问题变得多困难的分析。”

在那句话中，“更难”这个词故意含糊其辞，因为它既可以指处理时间，也可以指内存使用。

于 2008-11-21T16:21:33.833 回答
0

在计算机科学中，仅仅能够解决问题是不够的。它必须在合理的时间内解决。因此，在纯数学中，您提出了一个方程，而在 CS 中，您必须改进该方程，以便您可以在合理的时间内解决问题。

这是我能想到的最简单的表达方式，对于您的目的来说可能太简单了。

于 2008-11-21T16:39:33.097 回答
0

根据您拥有多长时间，也许最好从 DFA、NDFA 开始，然后证明它们是等效的。然后他们会理解 ND 与 D，并且会更好地理解正则表达式作为一个很好的副作用。

于 2008-11-21T17:19:48.693 回答