algorithm - 解释计算复杂性理论

Question

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

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

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

Answer 1

Hoooo，博士补偿倒叙。好的，开始吧。

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

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

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

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

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

(然后，数量呈指数级增长的克隆体开始战斗，决定杀死哪些克隆体。)

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

现在，还有一个概念:给定决策问题 P 和 Q，如果算法可以在多项式时间内将 P 的解转化为 Q 的解，则称 Q 是多时间可约 (或只是可还原)到 P。

一个问题是 NP 完全的，如果你能证明 (1) 它是 NP 的，并且 (2) 证明它是多时间可归约到一个已知的 NP 完全问题。 (其中困难的部分是提供 NP 完全问题的第一个示例:这是由 Steve Cook 在 Cook's Theorem 中完成的。)

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

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