1.1. 计算的极限¶

在整个学期的课程中，你研究了许多计算或语言表示模型： 有穷状态机（DFA、NFA、PDA）、正则表达式、文法和图灵机。 一般而言，我们的关键问题是： 给定的串是否属于给定的语言？ 我们如何对给定的语言进行分类？ 以及，两个模型的相对能力如何—它们识别的是相同的语言集合，还是不同？

所有这些问题都与"我们能做到……吗？"有关。 一般来说，所缺少的是对做某件事需要多长时间的考虑。

在之前的课程中，你可能已经学习了许多可以用于各种各样问题的数据结构，以及大量高效算法的例子。 一般来说，我们的查找算法力求在最坏情况下用 \(O(\log n)\) 时间找到一条记录， 排序算法则力求达到 \(O(n \log n)\)。 你可能遇到过一些渐近复杂度更高的算法。 无论是 Floyd 全对最短路径算法 还是标准矩阵乘法，其运行时间都为 \(\Theta(n^3)\) （不过对两者而言，由于都作用于 \(n \times n\) 矩阵，被处理的数据量为 \(\Theta(n^2)\)）。

我们之所以能高效地解决许多问题，是因为我们有（并且选择使用）高效的算法。 对于任何你知道某种算法的问题，总是有可能写出一个低效的算法来"解决"该问题。 例如，考虑一种排序算法，它逐一测试输入的所有排列，直到找到能提供有序列表的正确排列。 该算法的运行时间会高得不可接受，因为它与排列的数目成正比，对 \(n\) 个输入来说排列数为 \(n!\)。 在求解 最小代价生成树问题 时，如果我们要测试每一种可能的边子集以确定哪一个能形成最短的最小生成树，那么对于具有 \(|{\rm E}|\) 条边的图，工作量将与 \(2^{|{\rm E}|}\) 成正比。 幸运的是，对这两个问题我们都有更巧妙的算法，可以在（相对）较短的时间内找到答案，而无需显式地测试每一个可能的解。

遗憾的是，有许多计算问题，即使最佳可能的算法也需要很长的运行时间。 一个简单的例子是 汉诺塔问题， 它需要 \(2^n\) 次移动才能"解决"具有 \(n\) 个圆盘的塔。 任何解决汉诺塔问题的计算机程序都不可能以低于 \(\Omega(2^n)\) 的时间运行，因为必须输出那么多次移动。

在本章中，我们将考虑计算极限的某些方面。 首先，我们将考虑 归约 的概念，它告诉我们如何把一个问题的代价与另一个问题联系起来。 然后，我们将利用归约的概念来帮助理解一组称为 NP 完全问题 的问题。 这些问题之所以有趣，原因有很多： 它们数量众多，有许多实际的现实世界应用，而且我们不知道是否存在求解它们的高效算法。 甚至更奇怪的是：如果其中哪怕一个问题有高效的解法，那么 所有 这些问题都会有高效的解法。 对这些课题的研究被称为 计算复杂性理论。

当然，虽然运行时间很高的问题很糟糕，但根本无法解决的问题更加糟糕！ 这样的问题（被称为 不可解问题） 确实存在。 这类问题的经典例子是判定任意计算机程序在处理指定输入时是否会陷入无限循环。 这就是著名的 停机问题。 在本章结尾，我们将简要探索此类问题的理论，即 可计算性 理论。