解释计算复杂性理论

Question

假设有一些数学背景，你会如何向天真的人提供计算复杂性理论的总体概述？

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

有时，维基百科的编写方式就好像读者已经理解了所涉及的所有概念。

Answer 1

Hoooo，博士学位闪回。好的，这就是。

我们从一个决策问题的想法开始，一个算法总能回答的问题<！>“是<！>”;或<！> quot; no。<！> quot;我们还需要两种计算机模型（图灵机，真的）的概念：确定性和非确定性。确定性计算机是我们一直在思考的常规计算机;一个非确定性的计算机就像我们习惯的那样，除了具有无限的并行性之外，所以每当你进入一个分支时，你就会产生一个新的<！> quot; process <！> quot;检查双方。就像Yogi Berra说的那样，当你来到路上的叉子时，你应该接受它。

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

P中已知的问题在NP中是非常简单的 - 非确定性机器从不会麻烦自己分叉另一个过程，并且就像一个确定性的过程。已知存在P和NP都不存在的问题;一个简单的例子是枚举长度为n的所有位向量。无论如何，这需要2个 ⁿ 步骤。

（严格地说，如果节点终极机器可以在多时间内得到答案，则决策问题在NP中，并且确定性机器可以验证在聚合时间内解决方案是正确的。）

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

（然后，成倍数量的克隆人会争取解决哪些克隆必须被杀死。）

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

现在，还有一个概念：给定决策问题P和Q，如果算法可以在多项式时间内将P的解转换为Q的解，那么可以说Q是多时间可缩减的 （或者只是简化）到P。

如果你能证明（1）它在NP中，并且（2）表明它的多时间可以简化为已知为NP完全的问题，则问题是NP完全的。 （其中最难的部分是NP完全问题的第一个示例：这是由Steve Cook在库克定理。）

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

当且仅当它是<！>“至少为<！>”时，问题才是NP难的。很难完成NP完全问题。寻找最短路线的传统旅行商问题是NP难的，而不是严格的NP完全。

Answer 2

Michael Sipser 的计算理论导论是一本很好的书，非常易读。另一个伟大的资源是Scott Aaronson的 Great理论计算机科学的思想课程。

使用的形式主义是查看决策问题（是/否答案的问题，例如<！>“;此图表是否具有汉密尔顿循环<！>”;）<！>语言< ！> QUOT; - 字符串集 - 答案为是的输入。有一个关于<！>“计算机<！>”的正式概念。是（图灵机），如果有一个多项式时间算法用于在图灵机上确定该问题（给定输入字符串，说是或否），则问题出在P中。

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

它没有说明如何找到该证书。显然，您可以尝试<！>所有可能的证书<！>但这可能需要指数时间;目前尚不清楚你是否总是 要多于多项式时间来决定是或否;这是P vs NP问题。

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

另见这个问题： 什么是NP-complete in computer science？

但实际上，所有这些可能只对你含糊不清;值得花时间阅读，例如西普尔的书。这是一个美丽的理论。

Answer 3

这是对查理的帖子的评论。

  

如果你能证明（1）它在NP中，那么问题是NP完全的   （2）表明它的多时间可以减少到已知的问题   是NP完全的。

第二个条件有一个微妙的错误。实际上，你需要证明的是一个已知的NP完全问题（比如 Y ）是多项式时间可以减少到这个问题（我们称之为问题 X ）。

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

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

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

Answer 4

不幸的是，我所知道的最好的两本书（ Garey and Johnson 和 Hopcroft和Ullman ）都是从研究生证明导向开始的数学。这几乎肯定是必要的，因为整个问题很容易被误解或错误描述。杰夫当他试图接近这件事时，几乎被他的耳朵扯掉了...... folksy / jokey一个基调。

也许最好的方法是使用big-O表示法进行大量的实际工作使用大量的例子和练习。另请参见此答案。但请注意，这不是完全相同的事情：单个算法可以通过渐近线来描述，但是说问题具有一定的复杂性是关于每个可能的算法的声明为它。这就是证明如此复杂的原因！

Answer 5

我记得<！>“Computational Complexity <！> quot;从Papadimitriou（我希望我的名字拼写正确）作为一本好书

Answer 6

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

Answer 7

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

• P vp NP问题的克莱数学表述
• P 与 NP 页
• P、NP 和数学

如果您熟悉集合基数的概念，即集合中元素的数量，那么人们可以将这个问题视为 P 代表整数的基数，而 NP 是一个谜：它与所有实数的基数相同还是更大？

Answer 8

我简化的答案是：<！>“计算复杂性是分析当你添加更多元素时问题变得多难。<！>

在该句中，单词<！>“更难<！>”;故意模糊，因为它可能指的是处理时间或内存使用情况。

Answer 9

在计算机科学中，仅仅能够解决问题是不够的。它必须在合理的时间内解决。因此，在纯数学中，你想出了一个等式，在CS中你必须改进这个等式，这样你才能在合理的时间内解决问题。

这是我能想到的最简单的方法，这可能对你的目的来说太简单了。

Answer 10

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