计算机科学基础/计算的极限

计算的极限

我们已经研究了一些计算的重要思想，它使我们能够通过信息处理来执行惊人的任务。你可能已经产生了这样的印象：如果我们可以量化信息并设计算法，我们就可以使用计算来解决任何问题。在本章中，我们将研究有关计算极限的理论。在计算可以为我们做的事情方面，存在理论和实际限制。

图灵机再探

当我们讨论“算法”的正式定义时，我们引入了图灵机，它是一个用于计算的数学模型。通过这个模型，我们可以研究计算的本质，包括它可能做的事情。艾伦·图灵在他的模型机方面对可计算性理论做出了巨大贡献。他证明了图灵机与我们能构建的任何计算机一样强大（图灵完备性）。如果我们能找到图灵机无法解决的问题，我们就证明了该问题的解决方案不可计算，即该问题无法通过任何计算机上的计算来解决。

停机问题

1936 年，艾伦·图灵证明，对于所有可能的程序-输入对，解决停机问题的通用算法不存在，即停机问题无法通过计算来解决。更具体地说，停机问题是不可判定的，因为它是回答是或否（决策）问题的最简单类型的问题：给定一个输入，程序最终是否会停止（停止）。显然，实际运行程序并输入以查看它是否会停止是不可行的，因为它可能永远运行，如果程序中存在无限循环。这个想法是分析一个给定输入的程序，以确定它是否会停止。

艾伦·图灵通过一种称为反证法的证明技术证明了停机问题是不可判定的。回顾维基百科上的一些示例证明将非常有帮助。另一个经典的例子是数论中欧几里得定理的证明，该定理断言存在无限多个素数。所有反证法都从一个假设开始，即我们试图证明的命题是错误的，遵循一系列逻辑上有效的步骤，并得出明显错误或矛盾的结论，这也是错误的，因为一个命题可以是真或假，但不能同时是两者。

如果我们假设停机问题是可判定的/可解决的，那么我们应该能够设计一个算法并将其实现为一个程序，为我们解决这个问题。该程序应将程序和程序的输入作为输入参数，并返回答案——程序在输入上是否会停止。这样的程序可能听起来很奇怪，因为它将程序作为输入，但我们已经看到过这样的程序，例如，Snap! 中的高阶函数块将一个块（程序）作为输入，一个解释器程序将程序的源代码作为数据并运行程序。程序是数据，两者之间没有本质区别。以下证明表明，一个回答停机问题的程序是不存在的。

假设存在这样一个程序 A。A(P, D) -> 程序 P 在输入数据 D 上是否停止。
我们可以创建另一个程序 B，它将程序作为输入。在程序 B 内部，我们可以调用程序 A，将给定的输入作为输入，以确定输入程序是否会在自身作为输入数据时停止，如果答案为否（不会停止），我们停止（返回），如果答案为是（会停止），则无限循环。

 B(P):
   if A(P, P) = yes 
     infinite loop
   else
     return

如果我们将程序 B 本身作为输入提供给它会发生什么？或者更简单地说，程序 B 在自身上是否会停止？该练习有两个可能的结果：程序 B 在自身上停止或程序 B 在自身作为输入时永远运行。实际的结果/结果取决于程序 B 内部调用的程序 A 的结果。如果程序 B 在自身上停止，根据程序 B 的设计，它应该永远运行，因为程序 A 将程序 B 作为输入，应该运行无限循环。另一方面，如果程序 B 在自身上不会停止，那么程序 B 接收自身作为输入的输出应该立即返回。无论哪种方式都是一个矛盾。
到目前为止，我们做了一个假设，遵循了一系列逻辑上合理的步骤，最后得出了矛盾。哪里错了？矛盾不可能为真，因为它们在逻辑上是不可能的。这些步骤在逻辑上是合理的，唯一可能出错的部分是假设。因此，假设不可能为真，即停机问题是不可判定的。

这里有一个 YouTube 视频说明了证明：https://www.youtube.com/watch?v=92WHN-pAFCs

难以解决的问题

停机问题之所以困难，是因为它原则上甚至无法用算法解决。还有其他一些难题，原则上是可以解决的，但实际上它们几乎不可能解决。如你所见，我们可以根据最佳已知算法的性能对问题进行分类。如果一个问题可以使用快速算法解决，那么这个问题很简单，因为我们可以使用计算机快速解决它。相反，如果我们知道的最佳算法需要很长时间来解决问题，那么它就很难，因为计算机无法快速解决它。

使用算法复杂性理论，我们可以根据算法的复杂性将每个算法归入特定的类别。如果一个类别的 Big-O 表示法只包含多项式项，那么可以使用该类别中的算法解决的问题称为 P 问题（存在多项式时间解），例如 $O(1)$ 、 $log_{2}(N)$ $O(N)$ 和 $O(N^{2})$ 。P 问题是计算机容易解决的问题。在没有多项式时间解的问题中，有一些问题，如果我们可以猜测出解，就可以在多项式时间内验证它。例如，整数分解（或素数分解）问题没有已知的

我们将解决时间过长的问题统称为棘手问题，包括最佳算法时间复杂度为指数时间 ( $O(2^{N})$ ) 的问题，或者那些具有多项式时间解但指数过大的问题，例如 $O(N^{15})$ 。

如果一个问题的最佳算法解的时间复杂度为 $O(2^{N})$ ，当 $N=100$ 并且一台计算机每秒执行 $10^{12}$ 次运算，那么这台计算机需要 $4\times 10^{10}$ 年（相当于宇宙年龄）才能解决这个问题。

P 与 NP

显然，P 是 NP 的子集，因为 NP 的定义仅限于多项式时间验证答案，而在多项式时间内解决问题（P）当然符合这一条件。P 是否是 NP 的真子集，换句话说， $P=NP$ 是否成立，仍然是计算机科学领域的一个开放性问题。没有人知道答案。如果你能解决这个问题，你就可以获得一百万美元的奖金，这是千年大奖难题之一。

为了解决 P 与 NP 问题，理论计算机科学家定义了另一个类别，称为 NP 完全问题。这三个类别的关系如下图所示。

所有属于该类别的問題都是 NP 問題，它们共享一个特殊属性 - 所有其他 NP 完全问题都可以通过多项式时间进行转换/归约到每个 NP 完全问题。由于 NP 完备性的性质，如果我们能解决该类别中的任何一个问题，我们就能证明所有 NP 問題都可以在多项式时间内得到解决，即 $P=NP$ 。我们可以取任何 NP 問題，将其转化为已经解决的 NP 完全問題，并在多项式时间内解决该問題。总的时间仍然是多项式时间，因为多项式时间加上多项式时间仍然是多项式时间。已经发现了数千个 NP 完全问题，但没有一个得到解决。从某种意义上说，NP 完全问题是最难解决的已知问题。

大多数计算机科学家相信 $P\neq NP$ ，因为如果 P = NP，那么其后果将非常重大。“创造性飞跃”将消失，因为解决问题将变得像识别正确答案一样容易。大多数加密算法都是计算安全的，因为破解它们是 NP 問題 - 没有已知的多项式时间高效解决方案。如果 $P=NP$ ，那么所有的加密都会被破解。

计算机科学中还有其他未解决的问题。你可以在 https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science 中找到这些问题的列表。