解释计算复杂性理论

Question

解释计算复杂性理论

algorithmtheorycomplexity-theory

23

假设你有一些数学背景，你会如何向外行人概述计算复杂度理论？

我希望得到一个关于 P=NP 问题的解释。P是什么？NP又是什么？NP-Hard 又是什么？

有时维基百科描述问题时好像读者已经理解了所有相关概念。

- Mario Ortegón

在维基百科链接中，您可以找到P和NP定义的链接... - Gilles

10个回答

5

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

所使用的形式化方法是将决策问题（具有Yes / No答案的问题，例如“这个图是否有哈密顿回路”）看作是“语言” - 字符串集合 - 输入，其答案为Yes。有一个正式的概念来定义“计算机”（图灵机），如果存在一个多项式时间算法可以在图灵机上决定该问题（给定输入字符串，判断是Yes还是No），则该问题属于P。

如果问题可以在多项式时间内进行检查，则该问题属于NP，即对于答案为Yes的输入，可以提供一个（多项式大小的）证书，您可以在多项式时间内检查答案是否为Yes。 [例如，如果提供一个哈密顿回路作为证书，您显然可以检查它是否是一个哈密顿回路。]

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

如果能够解决该问题意味着能够解决NP中的所有问题，则该问题属于NP-hard。

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

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

- ShreevatsaR

5

这是对Charlie帖子的评论。

如果你能证明一个问题(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章。

- Raheem Rufai

我一直认为这只是一个小问题，因为必然地，“A可归约于B”意味着“B可归约于A”。 - Charlie Martin

@CharlieMartin 不，"A可约于B"并不意味着"B可约于A"。 - ShreevatsaR

4

很不幸，我所知道的最好的两本书（Garey and Johnson和Hopcroft and Ullman）都从研究生证明导向的数学水平开始。这几乎肯定是必要的，因为整个问题很容易被误解或错误描述。当杰夫试图以太过民间化/幽默化的语气处理这个问题时，他几乎被人咬掉了耳朵。

也许最好的方法就是通过大量实践使用大O符号使用大量示例和练习。另请参见这个答案。然而，请注意，这并不完全相同：单独的算法可以用渐近线来描述，但说一个问题具有某种复杂度是关于所有可能的算法的陈述。这就是为什么证明如此复杂的原因！

- jonrock

我实际上很喜欢杰夫关于NP完全性的写作。 - James McMahon

1

@James McMahon：这是一个有趣的帖子，但它也发生了一些事情 (a) 完全没有解释什么是 NP-完全 (b) 说一些惊人的、难以想象的错误，比如“没有人能够准确定义什么东西使问题成为 NP-完全”！当这一点被指出时，他添加了一个关于 P=NP 问题的更新，而事实上我们之所以能谈论 P=NP 问题，就是因为我们可以定义什么是 NP-完全问题。如果你读了评论，他还说了更可怕的垃圾话，比如“显然我们不能证明任何东西是 NP-完全的”(!)。 - ShreevatsaR

即使他对NP完备性的唯一描述是“花哨的计算机科学术语，简称‘难到极致’”，这也是错误的：存在比NP完备性更难的问题。很明显，他不理解NP类或完备性，更不用说NP完备性了，甚至没有读过他推荐的书的第一章（他承认了这一点）。实际上，如果你读他在第二页的评论，很神秘，他是没有理解这个想法，还是故意挑衅。 - ShreevatsaR

3

我记得Papadimitriou的“计算复杂度”是一本不错的书。

- flolo

1

谢谢你，你帮我省去了查找的麻烦。我记得那是一本很棒的书，只是数学方面有点深奥。 - Unsliced

1

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

- mfx

错误。如果我们知道“解决SAT的唯一方法是枚举所有可能的答案”，那么我们早就已经证明了P≠NP。 - ShreevatsaR

有比你所描述的尝试和错误方法更好的解决许多NP-Hard问题的方法。 P！= NP仅意味着不存在多项式时间算法。 - David Nehme

@shreevatsa：哦，请，这只是一个简化。正确地说，NP-hard意味着“你需要一个非确定性多项式时间算法”；但由于“非确定性”只是意味着“机器猜测正确的答案”，所以就是这样。 - mfx

@david：当然，对于大多数NP难题，有更好的方法（启发式算法）；但是这些启发式算法只适用于其中的一部分问题，而不是所有问题--否则你就将问题简化为比NP更容易的问题了。 - mfx

1

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

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

- JB King

0

我的简化回答是："计算复杂性分析的是，在增加更多元素时问题变得更难的程度。"

在这个句子中，"更难"这个词故意模糊不清，因为它可以指处理时间或者内存使用。

- benjismith

0

在计算机科学中，仅仅能够解决问题是不够的，这个问题必须在合理的时间内可解决。因此，尽管在数学领域你可以提出一个方程式，但在计算机科学中，你必须完善该方程式，以便能够在合理的时间内解决问题。

这是我能想到的最简单的表述方式，也许对您来说过于简单了。

- nemo

有趣的观察！（在计算机科学中，你必须优化那个方程式，以便能够在合理的时间内解决问题） - gpuguy

0

根据你的时间安排，也许最好从DFA、NDFA开始，然后展示它们的等效性。这样他们就能理解ND与D的区别，并且会因此更好地理解正则表达式。

- John the Statistician

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

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

- Seneca the Younger · Accepted Answer

噢，博士论文的回忆。好的，我们开始吧。

我们从决策问题的概念开始，这是一个算法可以始终回答“是”或“否”的问题。我们还需要计算机的两个模型（图灵机，确切地说）：确定性和非确定性。确定性计算机是我们平常想到的常规计算机；非确定性计算机与我们习惯的计算机一样，只不过具有无限并行性，因此每当你遇到一个分支时，就会生成一个新的“进程”并检查两侧。就像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完全问题的例子：这是由Cook's Theorem中的Steve Cook完成的。)

因此，实际上它的意思是，如果有人找到了一个多项式时间解决一个NP完全问题的方法，他们自动拥有了解决所有 NP完全问题的方法；这也意味着P=NP。

如果一个问题“至少和”一个NP完全问题一样难，则该问题是NP难问题。寻找最短路径的更常见的旅行商问题是NP难问题，而不是严格的NP完全问题。