对计算问题的分析取决于三个基本问题的答案：
1.什么是计算问题？将两个数相乘是一个计算问题；编写计算机程序以超越人类在写诗方面的能力也是。为了在发展计算问题分析的一般理论方面取得进展，我们将分离出一类被称之为判定问题的特殊问题，并将我们的分析集中在这些问题上。以这种方式做出限制使得一套优雅而又结构丰富的理论得以发展。最重要的是，这是一套其原理的应用远远超出判定问题的理论。
2.我们如何设计算法来解决给定的计算问题？一旦指定了一个问题，可以使用哪些算法来解决这个问题？是否存在一般的技术可用于解决各类问题？我们怎样才能确保算法的行为与声称的一样？
3.解决给定计算问题所需的最小资源是多少？运行算法需要消耗资源，例如时间，空间和能量。在不同的情况下，可能希望最小化一种或多种资源的消耗。我们能否根据解决问题所需的资源需求对问题进行分类？ 在接下来的几节中，我们将研究这三个问题，特别是问题 1 和问题 3 。虽然问题 1 ——什么是计算问题——也许是这些问题当中最基本的，但我们会把它的回答推迟到3.2.3节，首先在3.2.1节中建立与资源量化相关的一些背景概念，然后在 3.2.2 节中回顾计算复杂性的关键思想。
问题 2 ，如何设计好的算法，是众多研究人员大量创造性工作的领域。这些工作是如此之多，以至于在这个简短的介绍中，我们甚至无法开始描述好的算法设计当中所采用的主要思想。如果对这个美妙的课题感兴趣，我们推荐您跳到本章的末尾＂背景资料与延伸阅读＂。我们与这个课题最紧密的直接联系将发生在本书的后面，即当我们研究量子算法的时候。量子算法构造所需的技术通常涉及到经典计算机算法设计中已经存在的深刻思想，以及基于完全量子力学的算法设计创新。由于这个原因，也因为量子算法设计的精神在很多方面与经典算法设计如此相似，我们鼓励你至少要熟悉经典算法设计的基本思想。
问题 3，解决给定计算问题所需的最小资源是多少，这是接下来几个小节的主要关注点。例如，假设给我们两个长度为 $n$ 比特的数字，我们希望把它们相乘。如果在单带图灵机上执行乘法，那么图灵机必须执行多少次计算步骤才能完成任务？在完成任务时，使用了多少图灵机上的空间？
这些是我们可能会问的资源问题的例子。一般来说，计算机使用许多种不同的资源，然而我们会把大部分注意力集中在时间，空间和能量上。传统上，在计算机科学中，时间和空间一直是算法研究中两个主要的资源问题，我们在 3.2.2 节到 3.2.4 节中研究这些问题。能量一般是次要的考虑因素；然而，对能量需求的研究激发了可逆经典计算这一研究课题，这反过来又是量子计算的先决条件，因此我们在 3.2.5 节中详细地研究计算的能量需求。
不同的计算模型会导致不同的计算资源需求。即使是像从单带图灵机改为双带图灵机这样简单的事情都可能会改变求解一个给定的计算问题所需的资源。对于已经理解得非常透彻的计算任务，例如整数加法，这种计算模型之间的区别可能是令人感兴趣的。然而，对于理解一个问题的第一步，我们想要一种量化资源需求的方法，该方法独立于计算模型中相对平凡的变化。为此而
发展出来的工具之一便是渐近符号，它可用于概括函数的本质行为。例如，可以使用这种渐近符号来概括一个给定的算法运行时所需的时长的本质，而不必过多担心精确的时间。在本节中，我们将详细描述这种记号，并将其应用于一个简单的问题，用以说明计算资源的量化——把名字列表按字典序排序的算法的分析。
例如，假设我们对把两个 $n$ 位数加在一起所需的门的数量感兴趣。精确地计数所需的门的数量反而掩盖了重点：也许某个特定的算法需要 $24 n+2\lceil\log n\rceil+16$ 个门来执行这项任务。然而，在问题规模十分巨大这一限制下，唯一重要的项是 $24 n$ 。此外，我们忽视常数因子，因为其对算法的分析是次要的。该算法的本质行为被总结为其所需的操作数量的规模为 $n$ ，其中 $n$ 是要相加的数字的位数。渐近符号由三个工具组成，这使得这个记号更加精确。 $O$（＂大 $O$＂）记号用来设定函数行为的上界。假设 $f(n)$ 和 $g(n)$ 是非负整数上的两个函数。我们说＂$f(n)$ 在函数类 $O(g(n))$ 当中＂，或者＂$f(n)$ 是 $O(g(n))$ 的＂，如果存在常数 $c$ 和 $n_{0}$ ，使得对于所有大于 $n_{0}$ 的 $n, f(n) \leqslant c g(n)$ 。也就是说，对于足够大的 $n$ ，在相差一个不重要的常数因子的意义下，函数 $g(n)$ 是 $f(n)$ 的一个上界。大 $O$ 记号对于研究特定算法最坏情况下的行为特别有用，其中我们通常对找到一个算法消耗资源的上界感到满意。
在研究一类算法的行为时——比如可以用来把两数相乘的所有算法类——有必要界定所需资源的下界。为此，我们使用 $\Omega$（＂大 Omega＂）记号。函数 $f(n)$ 被称为是 $\Omega(g(n))$ 的，如果存在常数 $c$ 和 $n_{0}$ ，使得对于所有大于 $n_{0}$ 的 $n, ~ c g(n) \leqslant f(n)$ 。也就是说，对于足够大的 $n$ ，在相差一个不重要的常数因子的意义下，$g(n)$ 是 $f(n)$ 的一个下界。
最后，$\Theta$（＂大 Theta＂）记号用于表示在相差一个不重要的常数因子的意义下，$f(n)$ 的行为渐进地与 $g(n)$ 相同。也就是说，我们说 $f(n)$ 是 $\Theta(g(n))$ 的，如果它是 $O(g(n))$ 和 $\Omega(g(n))$ 的。
让我们考虑渐近符号的一些简单的例子。函数 $2 n$ 在 $O\left(n^{2}\right)$ 类中，因为对于所有的正整数 $n$ ， $2 n \leqslant 2 n^{2}$ 。函数 $2^{n}$ 是 $\Omega\left(n^{3}\right)$ 的，因为对于足够大的 $n, n^{3} \leqslant 2^{n}$ 。最后，函数 $7 n^{2}+\sqrt{n} \log n$ 是 $\Theta\left(n^{2}\right)$ 的，因为对于所有足够大的 $n, 7 n^{2} \leqslant 7 n^{2}+\sqrt{n} \log n \leqslant 8 n^{2}$ 。在下面的几个习题中，你会遇到渐近符号的一些基本的性质，这些性质使其成为算法分析的有力工具。
习题3.9 证明 $f(n)$ 是 $O(g(n))$ 的当且仅当 $g(n)$ 是 $\Omega(f(n))$ 的。由此推出 $f(n)$ 是 $\Theta(g(n))$ 的当且仅当 $g(n)$ 是 $\Theta(f(n))$ 的。
习题3.10 假定 $g(n)$ 是次数为 $k$ 的多项式。证明对任意 $l \geqslant k, g(n)$ 是 $O\left(n^{l}\right)$ 的。
习题 3.11 证明对任意 $k > 0, \log n$ 是 $O\left(n^{k}\right)$ 的。
习题3.12（ $n^{\log n}$ 是超多项式的）证明对任意的 $k, n^{k}$ 是 $O\left(n^{\log n}\right)$ 的，但是 $n^{\log n}$ 不可能是 $O\left(n^{k}\right)$ 的。
习题3.13（ $n^{\log n}$ 是亚指数的）证明对任意的 $c > 1, c^{n}$ 是 $\Omega\left(n^{\log n}\right)$ 的，但是 $n^{\log n}$ 不可能是 $\Omega\left(c^{n}\right)$ 的。
习题 3.14 假设 $e(n)$ 是 $O(f(n))$ 的，$g(n)$ 是 $O(h(n))$ 的。证明 $e(n) g(n)$ 是 $O(f(n) h(n))$ 的。
在资源量化中使用渐近符号的一个例子是在如下问题上的简单应用：把 $n$ 个名字的列表按照字典序排序。许多排序算法都基于＂比较和交换＂操作：比较 $n$ 元素列表中的两个元素，如果它们的顺序不对，则交换它们的位置。如果这种比较和交换的操作是我们访问列表的唯一方法，那么需要多少次这样的操作才能确保列表已经正确地排好序？
求解排序问题的一个简单的比较和交换算法如下：（注意，compare－and－swap（ $\mathrm{j}, \mathrm{k}$ ）比较编号为 $j$ 和 $k$ 的表项，如果它们的次序不对，则进行交换）
for j=1 to n-1
for k = j+1 to n
compare-and-swap ($\mathrm{j}, \mathrm{k}$ )
end $k$
end $j$
显然，该算法正确地将 $n$ 个名字的列表排列成字典序。注意，算法执行比较和交换操作的次数为 $(n-1)+(n-2)+\cdots+1=n(n-1) / 2$ 。因此，算法使用的比较和交换操作的次数是 $\Theta\left(n^{2}\right)$ 的。我们能比这个做得更好吗？事实证明我们可以。已知诸如＂堆排序＂之类的算法运行时只使用了 $O(n \log n)$ 次比较和交换操作。此外，在习题 3.15 中将完成一个简单的计数论证，证明任何基于比较和交换操作的算法都需要 $\Omega(n \log n)$ 次这样的操作。因此，一般地，排序问题需要 $\Theta(n \log n)$ 次比较和交换操作。
习题 3.15（基于比较和交换的排序的下界）假设一个 $n$ 元素列表通过采取一系列比较和交换操作排好了序。列表有 $n!$ 种可能的初始排序。证明在采取了 $k$ 次比较和交换操作之后，最多有 $2^{k}$ 个可能的初始排序会按照正确的顺序排好序。由此得出结论，需要 $\Omega(n \log n)$ 次比较和交换操作才能把所有可能的初始排序按照正确的顺序排好序。
任何算法都不能解决它这一想法——这是永远不会改变的根本性的事情——这个想法吸引着我。 －Stephen Cook 有时候，一些事情是不可能完成的是一件好事情。我很高兴有很多事情没有人可以对我做。 ——Leonid Levin 我们选择多项式算法作为刻画＂实际中有效的计算＂这一模糊观念的数学定义受到了来自各方的批评，这一点并不令人惊讶。［ $\cdots \cdots]$ 基本上，我们为我们的选择做的论证必定如下：采用多项式最坏情况下的表现作为我们衡量效率的标准会产生一个优雅而有用的理论，这个理论说明了一些关于实际计算的有意义的结论，而如果没有这种化简，这将是不可能的。
执行计算需要多少时间和空间资源？在许多情况下，这是我们关于计算问题可以询问的最重要的问题。像数的加法和乘法之类的问题被认为是可以高效求解的，因为我们有执行加法和乘法的快速算法，且它在运行时占用的空间很小。许多其他问题没有已知的快速算法，并且实际上不可能求解，这不是因为我们找不到求解问题的算法，而是因为所有已知的算法都需要消耗大量的空间或时间，以至于它们在实际中毫无用处。
计算复杂性研究求解计算问题所需的时间和空间资源。计算复杂性的任务是证明求解一个问题可能的最优算法所需资源的下界，即便我们未明确知晓这一算法。在本节和接下来的两节中，我们会概览计算复杂性，它的主要概念以及该领域的一些更重要的结果。注意，计算复杂性在某种意义上是对算法设计领域的补充；理想情况下，我们能够设计出的最高效的算法与计算复杂性所证明的下界完全匹配。不幸的是，情况往往并非如此。如前所述，在本书中我们不会深人研究经典算法的设计。
形式化计算复杂性理论的一个困难在于不同的计算模型可能需要不同的资源来解决相同的问题。例如，多带图灵机可以比单带图灵机快得多地解决许多问题。这一困难以相当粗略的方式被解决了。假设我们通过给出 $n$ 个比特作为输人指定了一个问题。例如，我们可能对一个特定的 $n$ 位数是否为素数感兴趣。计算复杂性的主要贡献在于它在可以使用关于 $n$ 的多项式的资源来解决的问题和需要使用比 $n$ 的任何多项式都增长得更快的资源的问题之间做出了区分。在后一种情况下，我们通常说所需的资源是问题规模的指数大小，这里我们滥用了术语＂指数的＂，因为存在像 $n^{\log n}$ 这样的函数，它比任何多项式都增长得更快（因此根据这个约定是＂指数的＂），然而它比任何真正的指数都增长得要慢。一个问题被认为是容易的，易解的或者可行的，如果存在一个使用多项式资源的算法求解该问题；而它被认为是困难的，难解的或者不可行的，如果最好的算法都需要使用指数的资源。
举个简单的例子，假设我们有两个整数，其二进制展开为 $x_{1} \cdots x_{m_{1}}$ 和 $y_{1} \cdots y_{m_{2}}$ ，我们希望确定这两个数的和。输入的总大小为 $n \equiv m_{1}+m_{2}$ 。很容易看出，使用数量为 $\Theta(n)$ 的基本运算可以把这两个数相加；该算法使用多项式（实际上是线性的）数量的操作来执行其任务。相比之下，人们相信把一个整数分解为它的素因子乘积的问题是难解的（尽管它从未被证明！）。也就是说，人们相信没有算法可以使用 $O(p(n))$ 的运算来对任意 $n$ 位整数进行素因数分解，其中 $p$ 是某个固定的 $n$ 的多项式。稍后我们会给出许多其他的例子，人们相信在上述意义下这些问题都是难解的。
多项式与指数的分类是相当粗糙的。在实际当中，使用 $2^{n / 1000}$ 次运算来求解问题的算法可能比使用 $n^{1000}$ 次运算的算法更加有用。仅仅对非常大的输人规模 $\left(n \approx 10^{8}\right)$ ，上述＂高效的＂多项式算法优于＂低效的＂指数算法，而出于许多目的，选择＂低效的＂算法可能更加实际。
然而，有许多理由将计算复杂性主要建立在多项式与指数分类的基础之上。首先，历史上，除少数例外，多项式资源的算法比指数算法快得多。我们可以推测其原因是缺乏想象力：提出需要 $n, n^{2}$ 或其他低阶多项式运算次数的算法通常比找到一个需要 $n^{1000}$ 次运算的自然的算法要容易得多，尽管类似后者的例子确实存在。因此，人类思维更容易提出相对简单的算法，这一倾向意味着在实际当中多项式算法通常比指数算法执行的效率要高得多。
强调多项式与指数分类的第二个和更基本的原因源自强丘奇－图灵论题。如 1.1 节所述，在
20 世纪 60 年代和 70 年代，人们观察到概率型图灵机似乎是最强大的＂合理＂计算模型。更确切地说，研究人员一致地发现，如果在某个不是概率型图灵机的计算模型下可以使用 $k$ 个基本运算计算某个函数，那么在概率型图灵机模型下，总是可以使用最多 $p(k)$ 个基本运算计算相同的函数，其中 $p(\cdot)$ 是某个多项式函数。这个陈述被称之为强丘奇－图灵论题：
强丘奇－图灵论题：任何计算模型都可以在概率型图灵机上进行模拟，且最多只需要增加多项式量级的基本运算次数。
强丘奇－图灵论题对于计算复杂性理论来说是个极好的消息，因为它意味着只需要把注意力集中在概率型图灵机计算模型上。毕竟，如果一个问题在概率型图灵机上没有多项式资源的解决方案，那么强丘奇一图灵论题意味着它在任何计算设备上都没有有效的解决方案。因此，强丘奇一图灵论题意味着如果把效率的概念等同于多项式资源的算法，计算复杂性的整个理论将会采用一种简洁的，与模型无关的形式，并且这种优雅性为接受＂可用多项式资源求解＂等同于＂高效求解＂提供了强大动力。当然，对量子计算机感兴趣的主要原因之一是，他们通过高效求解一个被认为在所有经典计算机上（包括概率型图灵机）难解的问题，对强丘奇－图灵论题提出了质疑！尽管如此，理解和欣赏强丘奇－图灵论题在寻找独立于模型之外的计算复杂性理论中所扮演的角色仍然是有用的。
最后，注意到在实践中，计算机科学家并不仅仅对问题的多项式与指数分类感兴趣。这仅仅是理解一个计算问题有多困难的第一个也是最粗糙的方式。然而，它是一个非常重要的区分，并阐明了许多关于计算机科学中资源问题的本质的更加广泛的观点。对于本书的大部分内容，它将成为我们评估一个给定算法的效率的核心关注点。
在研究了多项式与指数分类的优点之后，我们现在必须承认，计算复杂性理论有一个显著的缺陷：似乎很难证明存在能够引起人们兴趣的需要指数资源来求解的问题类。很容易给出大多数问题都需要指数资源的非构造性证明（参见下面的习题 3.16 ），此外人们猜想许多有趣的问题都需要指数资源才能得到它们的解，但是严格的证明似乎很难给出，至少以现阶段的知识是如此。计算复杂性的这一不足对量子计算具有重要意义，因为事实证明量子计算机的计算能力可能与经典计算复杂性理论中一些主要的开放问题有关。在这些问题得到解决之前，无法肯定地断言量子计算机在计算上有多么强大，甚至不能断言它是否比经典计算机更强大！
习题3.16（存在难以计算的函数）证明存在 $n$ 比特输人上的布尔函数，其需要至少 $2^{n} / n$ 个逻辑门才能计算。
许多计算问题往往有一个清晰的判定性问题的形式——一个答案为是或否的问题。例如，给定的整数 $m$ 是否为素数？这就是素性测试问题。计算复杂性问题往往容易被表述为判定性问题，有以下两个原因：理论研究往往先研究最简单形式的问题，然后将其推广至一般形式；以及从历史上看计算复杂性理论就源于对判定性问题的研究。
尽管大多数判定性问题都有一个简洁而相似的形式，对判定性问题的一般性质的讨论往往采用形式语言方面的术语。一个在字母表 $\Sigma$ 上的语言 $L$ 是集合 $\Sigma^{*}$ 的一个子集，其中 $\Sigma^{*}$ 是基于 $\Sigma$的所有（有限长度）字符串构成的集合。比如，当 $\Sigma={0,1}$ 时，所有偶数的二进制形式表示组成的集合，$L={0,10,100,110, \cdots}$ ，就是一个 $\Sigma$ 上的语言。
判定性问题可以用一种直接的方式被编码为语言上的问题。举例来说，素性测试问题的二进制编码方式如下：字母表 $\Sigma={0,1} ; \Sigma^{*}$ 中的所有字符串与所有非负整数自然对应。比如， 0010对应于数字 2 。语言 $L$ 包含了与素数对应的所有字符串。
为了解决素性测试问题，我们需要一个图灵机，它初始时刻将给定的整数 $n$ 写在输人纸带上，最终在输出纸带上给出结果（如果 $n$ 是素数输出＂是＂，反之输出＂否＂）。更确切地说，我们可以方便地修改之前（3.1.1 节）图灵机的定义：将停机状态 $q_{\mathrm{h}}$ 改为两个状态 $q_{\mathrm{Y}}$ 和 $q_{\mathrm{N}}$ ，分别表示＂是＂和＂否＂。其它方面图灵机的表现和之前一样，除了停止状态：它达到 $q_{\mathrm{Y}}$ 或 $q_{\mathrm{N}}$ 时停止。更一般地，一个语言 $L$ 被一个图灵机 $M$ 所判定，如果这个图灵机能够确定输人 $x$ 是否属于 $L$ ，即最终停在状态 $q_{\mathrm{Y}}$ 如果 $x \in L$ ，停在状态 $q_{\mathrm{N}}$ 如果 $x \notin L$ 。我们也称这两种情况出现时机器接受或拒绝输人 $x$ 。
为了确定一个数是否是素数，我们能算的多快呢？或者说，最快的素性测试图灵机是什么样的？我们称一个问题在类 $\operatorname{TIME}(f(n))$ 中，如果存在一个图灵机可以在 $O(f(n))$ 的时间内判定输人 $x$ 是否属于这个语言，其中 $n$ 是输入 $x$ 的长度。一个问题被称为多项式时间可解的，如果存在常数 $k$ 使得该问题在 $\operatorname{TIME}\left(n^{k}\right)$ 中。所有在 $\operatorname{TIME}\left(n^{k}\right)(k \geqslant 0)$ 类中的语言组成的集合，称为 P类。 P 是我们第一个复杂性类的例子。更一般地，一个复杂性类是由一些语言组成的集合所定义的。许多计算复杂性理论都关注各种复杂性类的定义，以及找出不同复杂性类之间的关系。
显然，存在多项式时间无法解决的问题。不幸的是，证明任何给定的问题不能在多项式时间内解决似乎是非常困难的，尽管猜想比比皆是！一个被认为不属于 P 的有趣的判定性问题的一个简单例子是素因子分解问题：
素因子分解问题：给定一个合数 $m$ 和 $l < m, m$ 是否含有比 $l$ 小的非平凡因子？
素因子分解问题的一个有趣属性是，如果有人声称答案为＂是＂，即 $m$ 确实具有小于 $l$ 的非平凡因子，那么他们可以通过展示这样一个因子来支撑这个观点，然后可以由第三方通过长除法有效地检查。我们称这样一个因子是 $m$ 有一个非平凡因子小于 $l$ 这一事实的一个证据。这种易于检查的证据的想法是接下来复杂性类 NP 定义中的关键思想。我们已将因子分解表述为判定问题，但你可以轻松验证该判定问题等同于查找一个数的素因子：
习题 3.17 证明当且仅当素因子分解的判定问题在 $\mathbf{P}$ 中时，存在用于求数 $m$ 的非平凡因子的多项式时间算法。
素因子分解问题是一个被称为 NP 的重要复杂性类别中的问题的一个例子。区分一个问题是否在类 NP 中取决于，问题的肯定回答可以在适当的证据的帮助下很容易地被验证。更严格的说，如果存在具有以下属性的图灵机 $M$ ，则语言 $L$ 在 NP 中：
1.如果 $x \in L$ 那么存在一个证据（一个字符串 $w$ ）使得当输人为 $x$－空白符 $-w$ 时，$M$ 运行 $|x|$的多项式量级的时间后在状态 $q_{\mathrm{Y}}$ 终止。
2.如果 $x \notin L$ 那么对所有试图充当证据的字符串 $w$ ，当输人为 $x$－空白符－$w$ 时，$M$ 运行 $|x|$ 的多项式时间后在状态 $q_{\mathrm{N}}$ 终止。 NP 的定义中存在一个有趣的不对称性。虽然我们必须能够快速判定 $x \in L$ 的一个可能的证据是否是真的证据，但是对 $x \notin L$ 则没有这一要求。例如，在素因子分解问题中，我们有一个简单的方法证明一个给定整数有一个小于 $m$ 的因子，但找一个证据证明给定整数没有小于 $m$ 的因子要困难得多。这一想法定义了 coNP，这是一种由所有对＂否＂实例存在证据的语言组成的类；显然，coNP 中的语言是NP 中语言的补集。 $P$ 和 NP 是什么关系呢？显然， P 是 NP 的子集。计算机科学中最著名的未解问题即是否存在在 NP 中却不在 $P$ 中的问题。这通常被称为 $P \neq N P$ 问题。大多数计算机科学家相信 $P \neq N P$ ，但是几十年过去了没有人能够证明这一点，故 $P=N P$ 的可能性依然存在。
习题 3.18 证明如果 $\operatorname{coNP} \neq N P$ 则 $P \neq N P$ 。
人们的第一印象是 $P \neq N P$ 猜想应该很容易解决。要了解这个问题的微妙之处，看几个 $P$和 NP 中具体问题的例子会很有帮助。我们来看一个图论中的例子。图论问题是判定性问题的一大来源。一个图是一个由顶点 $\left\{v_{1}, \cdots, v_{n}\right\}$ 以及连接顶点的边构成的有限集合，其中边用顶点对 $\left(v_{i}, v_{j}\right)$ 表示。从这里开始，我们只讨论无向图，即每条边中顶点对的顺序无关紧要；相对的，有向图中边的顶点对的顺序则有意义。一个典型的图的例子见图 3－9。
图 3－9 一个图的例子
图论中一个圈指一个顶点序列 $v_{1}, \cdots, v_{m}$ ，其中 $\left(v_{j}, v_{j+1}\right)$ 以及 $\left(v_{1}, v_{m}\right)$ 均为图中的边。一个圈是简单的，如果顶点序列中没有重复的顶点。一个哈密顿圈是一个包含图中所有顶点的简单圈。图 3－10 给了两个例子，分别为包含哈密顿圈和不含哈密顿圈的图。
图 3－10 左图包含一个哈密顿圈，即 $0,1,2,3,4,5,0$ 。观察可知右图不存在哈密顿圈 哈密顿圈问题（HC）是确定一个给定的图是否包含一个哈密顿圈。 HC 是 NP 中的一个判定性问题，因为如果一个给定的图包含一个哈密顿圈，那么这个圈就是一个易于检查的证据。更进
一步的，HC 目前没有一个多项式算法。事实上，HC 是一个被称为 NP 完全的复杂性类中的问题，这个类包含了 NP 中被认为是＂最难＂的问题——最难指若 HC 能在 $t$ 时间内被解决，那么 NP 中所有问题都可以在 $O(\operatorname{poly}(t))$ 时间内被解决。这也意味着任一 NP 完全问题可以在多项式时间内被解决，则 $\mathrm{P}=\mathrm{NP}_{\text {。 }}$
有一个形式上和 HC 相似，但实质完全不同的问题——欧拉回路问题。一条欧拉回路是图 $G$的一个边序列表示的圈，其中 $G$ 的每条边恰出现一次。欧拉回路问题（EC）是判定一个给定的 $n$顶点图 $G$ 是否含有一个欧拉回路。 EC 事实上和 HC 一样，除了对路径的要求从顶点变成了边。考虑如下定理，它将在习题 3.20 中被证明： 定理 3.1 （欧拉定理）一个连通图包含一条欧拉回路当且仅当它的每个顶点均有偶数条边相关联。
欧拉定理给出了一个解决 EC 的高效算法。首先，检查图是否联通；这很容易在 $O\left(n^{2}\right)$ 时间内实现，见习题 3.19 。如果图不连通，那么显然欧拉回路不存在。如果图是联通的，那么对每个顶点检查是否有偶数条边与之相关联。如果有顶点不满足这个条件，那么不存在欧拉回路，反之欧拉回路存在。因为有个 $n$ 顶点，$n(n-1) / 2$ 条边，这个算法需要 $O\left(n^{3}\right)$ 的基本操作。因此 $\mathrm{EC} \in \mathrm{P}$ 。不知道为什么在访问每条边的问题中存在一种数据结构，可以利用该数据结构来给出有效的算法，但这似乎没有相应的版本在访问每个顶点的问题中；为什么这种数据结构可以在一个例子中起作用，而在另一个中不行（也可能就没有），这一点并不显然。
习题3.19 可达性问题是判定图中特定两个点之间是否存在一条路径。证明可达性问题可以在 $O\left(n^{2}\right)$ 的时间内解决，其中 $n$ 是图的顶点数。用这个结果证明确定一个图是否连通可以在 $O\left(n^{3}\right)$的时间内解决。
习题3.20（欧拉定理）证明欧拉定理。特别的，如果每个顶点都有偶数条边相关联，给出一个构造性算法找出一条欧拉回路。
判定性素因子分解问题和素因子分解问题的等价性是计算机科学中最重要的思想之一——归约思想的一个特例。直觉上，我们知道某些问题可以被视为其他问题的特殊情况。归约的一个不那么平凡的例子是将 HC 归约到旅行商问题（TSP）。旅行商问题如下：给出 $n$ 个城市 $1,2, \cdots, n$和每对城市之间的非负整数距离 $d_{i j}$ 。给定一个长度 $d$ ，问题是判定是否存在总距离小于 $d$ 的游览所有城市的巡回路线。
归约过程如下。假设我们有一个 $n$ 顶点的图 $G$ 。我们将其转化为 TSP 问题的一个实例。将图的每个顶点视为一个＂城市＂，城市间的距离为 1 （若图中二点之间有边）或 2 （若图中二点之间无边）。这样一来一个长度小于 $n+1$ 的游览方案总距离一定是 $n$ ，对应于图中的一个哈密顿圈。另一方面，如果存在一个哈密顿圈，那么一定有长度小于 $n+1$ 的游览方案。通过这种方式，给定一个 TSP 的算法，我们可以将其转化为 HC 的算法，并且不需要太多额外的时间花费。这引出了下面两个结论。第一，如果 TSP 是简单的，那么 HC 也是；第二，如果 HC 是困难的，那么 TSP 也是。这是被称为归约的一般性技巧的一个实例：我们将问题 HC 归约到了问题 TSP。这个技术的使用将贯穿整本书。
关于归约更一般的概括见图 3－11。一个语言 $B$ 可以被归约到另一个语言 $A$ ，如果存在一个
图灵机在多项式时间内可以通过给定输人 $x$ 得到输出 $R(x)$ ，其中 $x \in B$ 当且仅当 $R(x) \in A$ 。因此，如果我们有一个判定 $A$ 的算法，我们只需要进行一点点额外的计算就可以判定 $B$ 。在这种意义下，语言 $B$ 的判定本质上不会比 $A$ 难。
图 3－11 从 $B$ 规约到 $A$
习题3.21（归约的传递性）证明如果语言 $L_{1}$ 可以被归约到语言 $L_{2}$ ，语言 $L_{2}$ 可以被归约到语言 $L_{3}$ ，则语言 $L_{1}$ 可以被归约到语言 $L_{3}$ 。
某些复杂性类中含有对应于该类的完全问题，即该复杂性类中＂最难＂判定的语言，精确来说就是该复杂性类中的任何其他语言都可以归约到此语言。不是所有的复杂性类都有完全问题，但是我们关心的几个类大部分都有。一个平凡的例子是 P 。令 $L$ 是 P 中任一非空及非全集的语言。则存在字符串 $x_{1}, x_{2}$ 使得 $x_{1} \notin L, x_{2} \in L$ 。那么任一 P 中的语言 $L^{\prime}$ 可以通过如下过程被归约到 $L$ ：给定输人 $x$ ，用多项式时间的判定性算法去决定 $x$ 是否属于 $L^{\prime}$ 。如果不是，令 $R(x)=x_{1}$ ，否则令 $R(x)=x_{2}$ 。
习题3.22 设 $L$ 是一个复杂性类的完全问题，并且 $L$ 可以被归约到该类中的另一个语言 $L^{\prime}$ 。证明 $L^{\prime}$ 也是该复杂性类的一个完全问题。
一个不平凡的例子，NP 也有完全问题。一个重要的例子以及所有其他 NP 完全问题的原型是电路可满足性问题（CSAT）：给定一个由与，或和非门组成的布尔电路，是否存在一组输人使得电路最终输出 1 ，亦即电路对某个输人可满足？CSAT 的 NP 完全性是著名的 Cook－Levin 定理，我们现在给出它的证明。
定理 3.2 （Cook－Levin）CSAT 是 NP 完全的。
证明 证明包含两部分。第一部分证明 CSAT 在 NP 里面，第二部分说明 NP 里面任意语言均可以被归约到 CSAT 。 这两部分的证明都基于模拟技术：第一部分本质上证明了一个图灵机可以高效模拟一个电路，第二部分本质上证明了一个电路可以高效模拟一个图灵机。这两部分的证明都十分直观；为了完整性我们给出第二部分证明的细节。
证明的第一部分是 CSAT 在 NP 中。给定一个包含 $n$ 个门的电路和一个潜在的证据 $w$ ，显然我们容易在多项式时间内运行一个图灵机检查 $w$ 是否满足这个电路，这证明了 CSAT 在 NP 中。
证明的第二部分是 NP 中的任意语言 $L$ 可以被归约到 CSAT。也就是说，我们的目标是建立一个多项式时间可计算的归约 $R$ 使得 $x \in L$ 当且仅当 $R(x)$ 是一个可满足的电路。假设 $M$ 是用于检查语言 $L$ 的输入－证据对 $(x, w)$ 的图灵机，归约的想法是找一个电路来模拟 $M$ 。电路的输入变量将代表证据 $w$ ；主要思想是查找一个符合电路的证据等价于对某个证据 $w, M$ 接受 $(x, w)$ 。不失一般性，为了简化构造我们对 $M$ 做以下的假设：
1.$M$ 纸带上的字母表只包含 $\triangleright, 0,1$ 和空白符。 2.$M$ 使用至多 $t(n)$ 的时间和 $s(n)$ 的空间运行，其中 $t(n), s(n)$ 均为 $n$ 的多项式。 3.事实上我们可以假设图灵机 $M$ 对所有长度为 $n$ 的输人运行时间均为 $t(n)$ 。这可以通过对每个 $x=\triangleright, 0,1$ 和空白符增加程序行 $\left\langle q_{\mathrm{Y}}, x, q_{\mathrm{Y}}, x, 0\right\rangle$ 和 $\left\langle q_{\mathrm{N}}, x, q_{\mathrm{N}}, x, 0\right\rangle$ ，最终保证机器在恰好 $t(n)$ 时间后停机。 $M$ 的模拟器构造的基本思想见图 3－12。图灵机中每一个内部状态在电路中被用一个比特变量来表示。我们命名对应的比特为 $\tilde{q}_{\mathrm{s}}, \tilde{q}_{1}, \cdots, \tilde{q}_{m}, \tilde{q}_{\mathrm{Y}}, \tilde{q}_{\mathrm{N}}$ 。开始的时候，$\tilde{q}_{\mathrm{s}}$ 赋值为 1 ，其它表示中间状态的比特均被赋值为 0 。图灵机纸带上每一单元格中包含三个比特：前两个比特表示当前该单元格处于哪一个字母（ $\triangleright, 0,1$ 或空白符），第三个为＂标志比特＂，如果读写头处于这一单元格则赋值为 1 ，反之则为 0 。我们将这些表示纸带上的字母内容的比特记为 $\left(u_{1}, v_{1}\right), \cdots,\left(u_{s(n)}, v_{s(n)}\right)$ ，标志比特记为 $f_{1}, \cdots, f_{s(n)}$ 。初始时比特 $u_{j}$ 和 $v_{j}$ 分别表示输入 $x$ 和 $w, f_{1}=1$ ，其他 $f_{j}=0$ 。除此之外再额外增加一个＂全局标识＂比特 $F$ ，它的功能将在后面解释。初始时将 $F$ 设置为 0 。对于整个电路，除了代表证据 $w$ 的比特作为变量，其他比特的值都是固定的。 $M$ 的动作为 $t(n)$ 次的＂模拟步骤＂，每一步模拟了图灵机一行程序的执行过程。每步的模拟又可以分解为依次对应于相应程序行的一系列步骤程序，并且最后一步将全局标志 $F$ 置为 0 ，如图 3－13 所示。为了完成模拟，我们只需要考虑形如 $\left\langle q_{i}, x, q_{j}, x^{\prime}, s\right\rangle$ 的程序行。为了方便起见，我们假设 $q_{i} \neq q_{j}$ ，因为当二者相等时的操作是类似的。操作步骤如下：
1.检查 $\tilde{q}_{i}=1$ 是否成立，这表示机器当前的状态为 $q_{i}$ 。
2.对纸带上每一个单元格：
（a）检查全局标识比特是否为 0 ，为 0 则表示图灵机还未采取任何动作；
（b）检查当前单元格的标识比特是否为 1 ，为 1 则表示纸带头处于此单元格；
（c）检查此单元格的内容比特是否为 $x$ ；
（d）如果以上所有检查均通过，则实施以下步骤：
i）赋值 $\tilde{q}_{i}=0, \tilde{q}_{j}=1$ ；
ii）将单元格内容比特更新为 $x^{\prime}$ ；
iii）更新此单元格和相邻单元格的标识比特，这取决于 $s$ 是三个值 ${-1,0,1}$ 中的哪一个，以及我们是否处于纸带的最左边。
iv）将全局标识变量置为 1 ，表示这一轮的计算已经完成。
这是一个固定的流程，仅和常数个比特相关。根据 3.1.2 节的通用性结论，这个过程可以被一个包含常数个门的电路所实现。
$t(n)$ 个模拟步骤
图 3－12 用电路模拟图灵机的过程概览
图 3－13 用电路模拟图灵机的步骤概览
容易证明整个电路所需要的电路门的个数为 $O(t(n)(s(n)+n))$ 。它关于问题规模是多项式量级的。在整个电路运行完毕后，$\tilde{q}_{Y}=1$ 当且仅当 $M$ 接受 $(x, w)$ 。因此这个电路是可满足的当且仅当图灵机 $M$ 接受 $(x, w)$ ，故我们完成了从 $L$ 到 CSAT 的归约。
CSAT 让我们在 NP 完全性的证明上迈出了第一步。我们不再需要根据定义去证明一个问题是 NP 完全的，而只需证明它是 NP 的并且 CSAT 可以归约到它。根据习题 3.22 这个问题一定是 NP 完全的。专题 3.3 讨论了一些 NP 完全问题的例子。另一个例子是可满足性问题（SAT），该问题以布尔公式的形式表示。让我们回忆一下，一个布尔公式 $\varphi$ 由以下元素组成：布尔变量集合 $x_{1}, x_{2}, \cdots$ ；布尔连接词，即具有一个或两个输人，一个输出的布尔函数，比如 $\wedge$（与），$\vee$（或）
和 $\neg$（非）；以及括号。对于给定的布尔变量，布尔公式的真假性基于布尔代数的基本规则确定。例如，公式 $\varphi=x_{1} \vee \neg x_{2}$ 当 $x_{1}=0, x_{2}=0$ 时为真，当 $x_{1}=0, x_{2}=1$ 时为假。可满足性问题就是确定对于一个给定的布尔公式 $\varphi$ ，是否存在满足此公式的输入。
习题3.23 通过以下步骤证明 SAT 是 NP 完全的：先证明 SAT 在 NP 中，再证明 CSAT 可以归约到 SAT。（提示：将实例中的每一条导线用布尔公式中不同的变量来表示将有助于归约。）
3SAT，SAT 的一个重要的带约束的特例，也是 NP 完全的。3SAT 中的布尔公式为 3－合取范式。一个公式被称为合取范式，如果它形式上为＂与＂连接的若干子句，每个子句形式为为 ＂或＂连接的若干文字，每个文字的形式为 $x$ 或 $\neg x$ 。例如，公式 $\left(x_{1} \vee \neg x_{2}\right) \wedge\left(x_{2} \vee x_{3} \vee \neg x_{4}\right)$ 是一个合取范式。一个公式是 3－合取范式，或 3－CNF，如果每个子句恰含 3 个文字。例如，公式 $\left(\neg x_{1} \vee x_{2} \vee \neg x_{2}\right) \wedge\left(\neg x_{1} \vee x_{3} \vee \neg x_{4}\right) \wedge\left(x_{2} \vee x_{3} \vee x_{4}\right)$ 是一个 3－合取范式。3－可满足性问题即是确定一个3－合取范式是否可以被满足。
3SAT 是 NP 完全的证明十分直观，但对于本讲来说有点长。相比较于 CSAT 和 SAT，3SAT在某种意义上更 NP 完全，并且它是无数其他问题 NP 完全性证明的基础。在关于 NP 完全性讨论的最后，我们给出一个令人惊讶的事实：如果将 3SAT 问题中每个子句中包含文字的个数改为 2 ，那么这个问题可以在多项式时间内解决。
习题3.24（2SAT 存在高效算法）假设 $\varphi$ 是一个以合取范式形式表示的布尔公式，并且每个子句中只包含 2 个文字。
1.按如下方式构建一张有向图 $G(\varphi): G$ 的顶点对应于 $\varphi$ 中的变量 $x_{j}$ 和它们的非 $\neg x_{j}$ 。有向边 $(\alpha, \beta)$ 存在当且仅当子句 $(\neg \alpha \vee \beta)$ 或 $(\beta \vee \neg \alpha)$ 在 $\varphi$ 中。证明 $\varphi$ 是不可满足的当且仅当存在一个变量 $x$ 使得在图 $G(\varphi)$ 中从 $x$ 到 $\neg x$ 和从 $\neg x$ 到 $x$ 的均存在路径。 2.证明对于给定的一个 $n$ 顶点的有向图 $G$ ，可以在多项式时间内判定顶点 $v_{1}$ 和 $v_{2}$ 是否连通。 3.给出一个求解 2SAT 问题的高效算法。
NP 类的重要性部分源于大量的计算问题现在都已经知道是 NP 完全的。我们不能在这里对这个主题进行完整的综述（参见＂背景资料与延伸阅读＂），但是下面的例子来自许多不同的数学领域，它们展示了已知 NP 完全问题的五彩纷呈。 －子团问题（图论）：无向图 $G$ 中的一个子团是指一个顶点的集合，其中任意两个顶点之间都有边。子团的规模是它所包含的顶点个数。给定一个整数 $m$ 和图 $G, G$ 中是否存在规模为 $m$ 的子团？ －子集和问题（算术）：给定一个正整数的有限集合 $S$ 和目标值 $t, S$ 是否包含一个子集，其内部元素之和为 $t$ ？ －0－1 整数规划问题（线性规划）：给定一个 $m \times n$ 的整数矩阵 $A$ 和一个 $m$ 维整数向量 $y$ ，是否存在一个 $n$ 维的 0－1 向量 $x$ 使得 $A x \leqslant y$ ？ －顶点覆盖问题（图论）：无向图 $G$ 的一个顶点覆盖是一个顶点子集 $V^{\prime}$ ，使得图中每一条边都至少有一个端点在 $V^{\prime}$ 中。给定整数 $m$ 和图 $G, G$ 是否存在一个顶点个数为 $m$的顶点覆盖 $V^{\prime}$ ？
在 $\mathrm{P} \neq \mathrm{NP}$ 的假设下，将可以证明存在非空的复杂性类 NPI（NP 中间问题），这类问题既不能使用多项式的资源解决，也不是 NP 完全的。显然，目前没有任何一个问题被证明属于 NPI （否则我们就证明了 $\mathrm{P} \neq \mathrm{NP}$ ）。但是我们有一些候选的问题，其中两个最有可能的候选题是素因子分解问题和图同构问题：
图同构：假设 $G$ 和 $G^{\prime}$ 是两个顶点集为 $V \equiv\left\{v_{1}, \cdots, v_{n}\right\}$ 的无向图。 $G$ 和 $G^{\prime}$ 同构吗？亦即，是否存在一个双射 $\varphi: V \rightarrow V$ 使得边 $\left(v_{i}, v_{j}\right)$ 在 $G$ 中当且仅当边 $\left(\varphi\left(v_{i}\right), \varphi\left(v_{j}\right)\right)$在 $G^{\prime}$ 中？
由于两个原因让量子计算和量子信息的研究人员对 NPI 中的问题很感兴趣。首先，人们希望找到快速量子算法来解决不在 P 中的问题。其次，许多人怀疑量子计算机不能有效地解决 NP 中的所有问题，特别是 NP 完全问题。因此，关注 NPI 类是一件很自然的事情。实际上，已经发现了一种用于整数素因子分解的快速量子算法（第 5 章），这促使人们寻找快速量子算法来解决其他疑似在 NPI 中的问题。
我们已经研究了某些重要复杂性类的一些基本属性。存在一个名副其实的关于复杂性类的万神殿，并且复杂性类之间存在着许多已知的或疑似的非平凡关系。对于量子计算和量子信息的研究来说，没有必要理解所有已经定义的不同复杂性类。然而，对更重要的复杂性类有所了解是很有用的，其中许多复杂性类在量子计算和量子信息研究中具有自然的对应物。此外，如果我们要了解量子计算机有多强大，那么我们有必要弄清楚量子计算机上可解决的问题类如何对应到为经典计算机中定义的复杂性类中。
在复杂性类的定义中本质上有三个可以改变的基本属性：感兴趣的计算资源（时间，空间， $\cdots \cdots$.$) ，所考虑问题的类型（判定问题，优化问题，……），以及底层计算模型（确定性图灵机，$概率图灵机，量子计算机，……）。毫不奇怪，这给我们提供了一个巨大的自由度来定义复杂性类。在本节中，我们将简要回顾一些更重要的复杂性类和它们的一些基本属性。我们从一个将感兴趣的资源由时间变为空间而定义出的复杂性类开始。
最自然的被空间条件约束的复杂性类是 PSPACE，这个类中的问题可以被一台图灵机使用多项式数目的工作比特完成，而对于使用的时间并没有做要求（见习题 3.25 ）。显然， P 在 PSPACE中，因为一台在多项式时间内停机的图灵机只能使用多项式数量的纸带单元格。进一步地，NP也是 PSPACE 的子集。为了证明这一点，假设 $L$ 是 NP 中的任一语言。假设规模为 $n$ 的问题有规模至多为 $p(n)$ 的证据，其中 $p(n)$ 是 $n$ 的某个多项式。为了确定这个问题是否有解，我们可以检查所有 $2^{p(n)}$ 种可能的证据。每次检查需要多项式的时间。如果每次测试过后我们立刻清空纸带上的数据，那么我们就可以在多项式空间完成检查。
不幸的是，目前还不知道 PSPACE 是否包含不在 P 中的问题！这是一个非常值得注意的现状一一很显然拥有无限时间和多项式空间资源的图灵机应该比仅具有多项式时间的机器更强大。然而，尽管人们付出了相当大的努力，这一点从未被证明。稍后我们将看到，在量子计算机上多项式时间内可解的问题类是 PSPACE 的一个子集，因此证明在量子计算机上有效解决的问题在经典计算机上无法有效解决将证明 P $\neq$ PSPACE，从而解决了计算机科学的一个重大悬而未决的问题。从乐观的角度来说，量子计算的思想可能有助于证明 $\mathrm{P} \neq \mathrm{PSPACE}$ 。悲观地说，人们可能会得出结论，要想严格证明量子计算机可以用来有效地解决在经典计算机上难以解决的问题还需要很长的时间。更悲观的是，有可能 $\mathrm{P}=\mathrm{PSPACE}$ ，在这种情况下量子计算机相比经典计算机没有任何优势！然而，极少（如果有的话）计算复杂性专家认为 $\mathrm{P}=\mathrm{PSPACE}$ 。
习题 3.25 （PSPACE $\subseteq$ EXP）复杂性类 EXP（指数时间复杂性类）包含了所有可以在图灵机上用指数时间（即 $O\left(2^{n^{k}}\right)$ 的时间，其中 $k$ 为任意常数）解决的判定性问题。证明 PSPACE $\subseteq$ EXP。（提示：如果一台图灵机包含 $l$ 个中间状态，字母表有 $m$ 个字母，并使用 $p(n)$ 的运行空间，证明它可以至多有 $l m^{p(n)}$ 个不同状态，并且如果图灵机不想陷人死循环，则必须在访问同一状态两次前停机。）
习题 $3.26 ~(~ L \subseteq P$ ）复杂性类 L（对数空间复杂性类）包含了所有可以在图灵机上用对数空间 （即 $O(\log (n))$ 的空间）解决的判定性问题。更准确的说，类 L 由一个双带图灵机所定义。第一条纸带包含了问题的一个规模为 $n$ 的实例，并且是只读的，即程序不允许改变此纸带上的内容。第二条纸带为工作带，初始时所有单元格均为空白符。工作纸带被限制只能使用对数的空间。证明 $\mathrm{L} \subseteq \mathrm{P}$ 。
给更多的时间和空间会增强计算能力吗？对每种情形答案都是肯定的。严格来说，时间层次定理表明 $\operatorname{TIME}(f(n))$ 是 $\operatorname{TIME}\left(f(n) \log {}^{2}(f(n))\right)$ 的真子集。类似的，空间层次定理表明 $\operatorname{SPACE}(f(n))$是 $\operatorname{SPACE}(f(n) \log (f(n)))$ 的真子集。这里 $\operatorname{SPACE}(f(n))$ 是指包含所有可以用 $O(f(n))$ 空间来判定的语言的复杂性类。层次定理在复杂性类的等价性类方面有很多有趣的应用。我们知道
$$ \begin{equation*} \mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXP} \tag{3.1} \end{equation*} $$
不幸的是，尽管每个包含关系都被相信是严格的，但没有一个能被证明。不过，时间层次定理指出 P 是 EXP 的严格真子集，空间层次定理指出 L 被 PSPACE 严格包含！故我们可以得出结论，式（3.1）中至少存在一个严格包含关系，虽然我们不知道是哪一个。
一旦我们知道一个问题是 NP 完全的，或者满足某些更难的标准，我们应该怎么处理？事实证明，这远不是算法复杂度分析的终点。一种可能的解决方案是确定哪些特殊情况可能是能够解决的。例如，在习题 3.24 中，我们看到 2SAT 问题具有高效算法，尽管 SAT 问题是 NP 完全的。另一种方式是改变正在考虑的问题类型，这种策略通常会导致新复杂性类的定义。例如，我们可以尝试找到好的算法去给出问题的一个近似解，而非去找到 NP 完全问题的精确解。例如，顶点覆盖问题是 NP 完全问题，但在习题 3.27 中，我们证明可以有效地找到最小顶点覆盖的一个近似比至多为 2 的近似值！而另一方面，在问题 3.6 中我们将证明，除非 $P \neq N P$ ，否则不可能找到 TSP 问题的任何因子内的近似解。
习题3.27（顶点覆盖问题的近似算法）设 $G=(V, E)$ 是一个无向图。证明以下算法可以为 $G$找到一个大小至多为最小顶点覆盖集的 2 倍的顶点覆盖：
$V C=\emptyset$
$E^{\prime}=E$
do until $E^{\prime}=\emptyset$
let $(\alpha, \beta)$ be any edge of $E^{\prime}$
$V C=V C \cup{\alpha, \beta}$
remove from $E^{\prime}$ every edge incident on $\alpha$ or $\beta$
return $V C$
为什么对一些 NP 完全问题可以找到近似解，而另一些则不行？毕竟，我们不是可以高效地将一个问题转化为另一个吗？这当然是对的，但是这种转换不一定保留了对原来的解的＂良好近似＂性质。因此，关于 NP 类中问题的近似算法的计算复杂性理论具有超出 NP 本身的结构。存在一套近似算法的完整的复杂性理论，遗憾的是它超出了本书的范围。然而，基本思想是定义一种归约概念，其能够以某种保持良好近似性的方式有效地将一个近似问题归约到另一个近似问题。利用这一概念，就可以通过类比 NP 类来定义诸如 MAXSNP 等复杂性类，MAXSNP 是所有可以有效验证该问题的近似解的问题集合。MAXSNP 存在完全问题，就像 NP一样，确定 MAXSNP和有效可解的近似问题类之间是什么关系是一个有趣的未解问题。
我们用一个复杂性类来结束本部分的讨论，这个复杂性类是通过改变底层的计算模型所引出。假设图灵机具有掷硬币的能力，可以使用硬币投掷的结果来决定在计算期间采取哪个动作。这种图灵机可能只能以一定的概率接受或拒绝输入。复杂性类 BPP（有界错误率概率多项式时间复杂性类）包含了所有可以被概率型图灵机 $M$ 所接受的语言 $L$ ，即如果 $x \in L$ 则 $M$ 以至少 $3 / 4$的概率接受 $x$ ，如果 $x \notin L$ 则 $M$ 以至少 $3 / 4$ 的概率拒绝 $x$ 。下面这个习题表明常数 $3 / 4$ 可以任意改变：
习题3.28（BPP 定义中常数的任意性）假设 $k$ 是一个固定的常数满足 $1 / 2 < k \leqslant 1$ 。假设 $L$是一个语言满足存在一台概率型图灵机 $M$ 使得如果 $x \in L$ 则 $M$ 以至少 $k$ 的概率接受 $x$ ，如果 $x \notin L$ 则 $M$ 以至少 $k$ 的概率拒绝 $x$ 。证明 $L \in \mathrm{BPP}$ 。
事实上，在专题 3.4 中讨论的切诺夫界（Chernoff bound）意味着只需要多重复几次用来判定 BPP 中语言的算法其成功的概率就可以被放大，就所有的意图和目的而言可以认为最终放大到 1 。基于这个原因，相较于 P，BPP 被认为是在经典计算机上能够有效解决的一类判定问题，而它在量子计算机上对应的类——被称为 $B Q P$ ——是我们在量子算法研究中最感兴趣的课题。
假设对一个判定性问题我们有一个算法，其给出正确结果的概率为 $1 / 2+\epsilon$ ，而给出错
误结果的概率为 $1 / 2-\epsilon$ 。如果我们运行这个算法 $n$ 次，那么看起来正确结果出现的次数应该会多一些。这个想法的依据是什么？切诺夫界回答了这一问题，它是初等概率论中一个朴素的结果。
定理3.3（切诺夫界）设 $X_{1}, \cdots, X_{n}$ 为独立同分布的随机变量，每个以概率 $1 / 2+\epsilon$ 取值为 1 ，以概率 $1 / 2-\epsilon$ 取值为 0 。则
$$ \begin{equation*} p\left(\sum_{i=1}^{n} X_{i} \leqslant n / 2\right) \leqslant \mathrm{e}^{-2 \mathrm{\epsilon}^{2} n} \tag{3.2} \end{equation*} $$
证明 考虑任一包含至多 $n / 2$ 个 1 的序列 $\left(x_{1}, \cdots, x_{n}\right)$ ，当这个序列恰好包含 $\lfloor n / 2\rfloor$ 个 1 时出现的概率最大，故
$$ \begin{align*} p\left(X_{1}=x_{1}, \cdots, X_{n}=x_{n}\right) & \leqslant\left(\frac{1}{2}-\epsilon\right)^{\frac{n}{2}}\left(\frac{1}{2}+\epsilon\right)^{\frac{n}{2}} \tag{3.3}\\ & =\frac{\left(1-4 \epsilon^{2}\right)^{\frac{n}{2}}}{2^{n}} \tag{3.4} \end{align*} $$
至多有 $2^{n}$ 个这样的序列，故
$$ \begin{equation*} p\left(\sum_{i} X_{i} \leqslant n / 2\right) \leqslant 2^{n} \times \frac{\left(1-4 \epsilon^{2}\right)^{\frac{n}{2}}}{2^{n}}=\left(1-4 \epsilon^{2}\right)^{\frac{n}{2}} \tag{3.5} \end{equation*} $$
最后，由简单的微积分知识 $1-x \leqslant \exp (-x)$ ，因此
$$ \begin{equation*} p\left(\sum_{i} X_{i} \leqslant n / 2\right) \leqslant \mathrm{e}^{-4 \epsilon^{2} n / 2}=\mathrm{e}^{-2 \epsilon^{2} n} \tag{3.6} \end{equation*} $$
这告诉我们对于固定的 $\epsilon$ ，出错的概率以算法重复次数的指数速度下降。在 BPP 的定义中我们取 $\epsilon=1 / 4$ ，因此仅需重复几百次算法即可将出错的概率减少到 $10^{-20}$ 以下，此时计算机的某个元件出故障的概率都比算法出错的概率大。
计算复杂性研究解决计算问题所需的时间和空间总量。另一个重要的计算资源是能量。在本节中，我们研究计算所需要的能量。令人惊讶的是，经典和量子计算原则上都可以在不消耗任何能量的情况下完成！计算中的能量消耗与计算的可逆性密切相关。考虑一个与非门，其包含两个输人位和一个输出位。该门本质上是不可逆的，因为在给定门的输出的情况下，输入不是唯一确定的。例如，如果与非门的输出为 1 ，那么输人可以是 $00,01,10$ 中的任何一个。另一方面，非门是可逆逻辑门的一个例子，因为给定了非门的输出，我们能够唯一推断出输人是什么。
理解不可逆转性的另一种方法是从信息消除的角度来考虑它。如果逻辑门是不可逆的，那么当门工作时，输人到该门的某些信息将不可避免地丢失——也就是说，一些信息已被逻辑门擦除了。相反在可逆计算中，不会擦除任何信息，因为输人始终可以从输出中恢复。因此，说计算是可逆的等同于说在计算过程中没有信息被擦除。
能耗与计算中的不可逆性之间有什么联系？兰道尔原理（Landauer＇s principle）提供了连接二者的桥梁，它指出为了擦除信息必须要消耗能量。更确切地说，兰道尔原理可以陈述如下：
> 兰道尔原理（第一种形式）：假设一台计算机擦除了 1 比特的信息，那么耗散到整个环境中的能量至少是 $k_{B} T \ln 2$ ，其中 $k_{B}$ 是玻尔兹曼常数，$T$ 是电脑工作环境的温度。
> 根据热力学定律，可以给出兰道尔原理另一种基于嫡耗散的形式，而不是能量耗散形式：
兰道尔原理（第二种形式）：假设一台计算机擦除了 1 比特的信息，那么整个环境的 摘至少增加了 $k_{B} \ln 2$ ，其中 $k_{B}$ 是玻尔兹曼常数。 兰道尔原理的证明是一个物理学问题，它超出了本书的范围——如果你想理解为什么兰道尔原理成立，请参阅本章末的＂背景资料与延伸阅读＂。但是，如果我们接受兰道尔原理，那么它会引出许多有趣的问题。首先，兰道尔原理仅给出了擦除信息所必须消耗的能量下限。现在的计算机距离该下限有多近？答案是并不是很接近——2000年左右计算机执行一个基本逻辑运算需要消耗大约 $500 k_{B} T \ln 2$ 的能量。
尽管现有的计算机远远达不到兰道尔原理设定的极限，但了解能耗可以减少多少仍然是一个有趣的基本问题。除了问题本身之外，该问题在实际应用中令人感兴趣的一个原因来自摩尔定律：如果计算机的能力不断增加，那么耗散的能量也必然增加，除非每次操作消耗的能量下降的速度至少和计算能力增长的速度一样快。
如果所有计算都可以可逆地完成，则兰道尔原理意味着计算机消耗的能量没有下限，因为在可逆计算期间根本不会擦除任何比特。当然，某些其他物理原理可能规定在计算过程中耗散能量；幸运的是，事实并非如此。但是有可能在不删除任何信息的情况下执行通用计算吗？物理学家可以在这个问题上作弊，预先直接看到这个问题的答案必然是肯定的，因为我们目前对物理定律的理解是它们从根本上是可逆的。也就是说，如果我们知道闭合物理系统的最终状态，那么物理定律会使我们可以计算出系统的初始状态。如果我们认为这些定律是正确的，那么我们必能得出结论：在像与门和或门这样的不可逆逻辑门中，必然隐藏着一些潜在的可逆计算性。但这隐藏的可逆性在哪里，我们可以用它来构建显式的可逆计算机吗？
我们将使用两种不同的技术来提供能够进行通用计算的可逆电路模型。第一个模型是一台完全由台球和镜子构成的计算机，它很好地具体展示了可逆计算的原理。第二个模型基于一个被称为 Toffoli 门的可逆逻辑门（我们在 1.4.1 节中首次遇到），它是一个更加抽象的可逆计算视角，稍后在我们讨论量子计算时会有很大的用处。也可以构建通用计算的可逆图灵机；但是，我们不会在这里研究这些，因为可逆电路模型对量子计算更有用。
台球计算机的基本思想如图 3－14 所示。台球从左侧＂输人＂计算机，在镜子间进行碰撞和反弹，然后在右侧＂输出＂。在可能的输人位置处是否存在台球分别代表逻辑 1 或逻辑 0 。这个模型
的迷人之处在于只要它的操作是基于经典力学的规律，它就明显地具有可逆性。此外，该计算模型在模拟标准电路计算模型上的任意计算的意义下被证明是通用的。
图 3－14 一个简单的有三个输人位和三个输出位的台球计算机，以及球从左侧输人和从右侧输出的展示。台球的存在或不存在分别用 1 或 0 表示。空圆圈表示由于碰撞导致的潜在路径。这个特定的计算机实现了 Fredkin 经典可逆逻辑门，此门会在后文中讨论
当然，如果真的建造了一个台球计算机，它将非常不稳定。就像任何台球运动员都可以证明的那样，在平滑表面上无摩擦地滚动的台球很容易被小的扰动干扰。台球计算模型取决于完美的操作，并且没有外部扰动——例如由热噪声引起的外部扰动。可以执行定期校正，但是必须额外执行工作去消除通过这样做获得的信息。因此，能量消耗用于降低对噪声的敏感性之目的，这对实用的真实计算机来说是必需的。对于本节的介绍来说，我们将忽略噪声对台球计算机的影响，并集中精力理解可逆计算的基本要素。
上述台球计算机为实现被称为 Fredkin 门的可逆通用逻辑门提供了一种优雅的方法。的确， Fredkin 门的特性提供了可逆逻辑门和电路的一般原理的有益概述。Fredkin 门有三个输入比特和三个输出比特，我们分别用 $a, b, c$ 和 $a^{\prime}, b^{\prime}, c^{\prime}$ 来表示。比特 $c$ 是一个控制比特，其值在 Fredkin 门作用后不会发生改变，即 $c^{\prime}=c 。 c$ 被称为控制比特的原因是它控制着其他两个比特 $a$ 和 $b$ 的改变。如果 $c$ 的值是 0 ，则 $a$ 和 $b$ 不变，即 $a^{\prime}=a, b^{\prime}=b$ 。如果 $c$ 的值是 1 ，则 $a$ 和 $b$ 进行交换，即 $a^{\prime}=b, b^{\prime}=a$ 。图 3－15 展示了 Fredkin 门的真值表。很容易看出 Fredkin 门是可逆的，因为给定了输出 $a^{\prime}, b^{\prime}, c^{\prime}$ ，我们可以确定输人 $a, b, c_{\circ}$ 事实上，为了恢复原始的输人，我们只需要在 $a^{\prime}, b^{\prime}, c^{\prime}$上作用另一个 Fredkin 门。
习题 3.29 （Fredkin 门的可逆性）证明连续作用两次 Fredkin 门后输出将和输人相同。
检查图 3－14 中的台球路径，不难发现这台台球计算机确实实现了 Fredkin 门：
习题 3.30 验证这台台球计算机实现了 Fredkin 门。
除了可逆性之外，Fredkin 门还具有一个有趣的特性，即在输入和输出之间保持 1 的数目不变。对于台球计算机而言，这相当于进人 Fredkin 门的台球的数量等于出来的数量。因此，有时将其称为保守的可逆逻辑门。这种可逆性和保守性对于物理学家来说很有趣，因为它们可能由基本的物理原理导致。自然定律是可逆的，可能的例外是量子力学的测量假设，在 2.2.3 节中讨论
过。保守性可以被认为类似于质量守恒或能量守恒等性质。实际上，在台球计算机模型中，保守性完全对应于质量守恒。
| 输入 | 输出 | ||||
|---|---|---|---|---|---|
| $a$ | $b$ | $c$ | $a^{\prime}$ | $b^{\prime}$ | $c^{\prime}$ |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
图 3－15 Fredkin 门的真值表和它的电路表示。如果控制位 $c$ 为 1 则比特 $a$ 和 $b$ 交换，否则不发生改变
Fredkin 门不仅具有可逆性和保守性，它同时也是一个通用的逻辑门！图 3－16展示了 Fredkin门可以被组合起来去模拟与门，或门，交叉和扇出函数，因此它可以被组装起来去模拟任意形式的经典电路。
图 3－16 Fredkin 门去模拟实现与门（左），或门（中）和交叉（右）这些基本门。中间的门也用于执行扇出操作，因为它在输出端产生两个 $x$ 副本。请注意，这些电路中的每一个都需要使用初始为标准态的额外＂辅助＂位一一例如，与门的第一行上的 0 输人——并且输出中通常包含剩余计算不需要的＂垃圾＂
为了使用 Fredkin 门模拟不可逆的门，例如与门，我们利用了下面两个想法。首先，我们允许在准备阶段输人辅助比特（ 0 或 1 ）到 Fredkin 门。其次，Fredkin 门的输出包含计算结果之外所不需要的多余＂垃圾＂。这些辅助比特和冗余比特对计算过程并不直接影响，它们的重要性在于使得计算可逆。的确，像与门和或门等不可逆的门可以被视为辅助比特和冗余比特被＂隐藏＂的可逆门。总而言之，给定任何计算函数 $f(x)$ 的经典电路，我们可以构造一个完全由 Fredkin门组成的可逆电路，该电路的输人由 $x$ 和一些处于标准态的辅助比特 $a$ 组成，计算 $f(x)$ 和一些额外的＂冗余＂比特 $g(x)$ 。我们将这个计算过程用 $(x, a) \rightarrow(f(x), g(x))$ 表示。
现在我们知道了如何可逆地计算函数。不幸的是，这一计算过程会产生不需要的无用比特。经过一些修改后，计算过程结束后可以使得所有产生的无用比特都处于标准状态。这种构造对量子计算至关重要，因为取值会依赖于输人 $x$ 的无用比特通常会破坏对量子计算至关重要的干涉属性。为了理解其工作原理，方便起见假设非门在我们的可逆门电路中可以使用，所以我们也可以假设辅助位 $a$ 开始时全部为 0 ，并且在必要时添加非门以将辅助比特从 0 变为 1 。假设我们也可以使用经典的受控非门（这个门以类似于 1.3.2 节的量子定义的方式定义，即其将 $(c, t)$ 变成 $(c, t \oplus c)$ ，其中 $\oplus$ 是模 2 的加法。）注意到当 $t=0$ 时有 $(c, 0) \rightarrow(c, c)$ ，故受控非门可以看成扇出门的可逆版本，并且不会在输出中遗留无用比特。
利用在电路开始处添加的非门，计算过程可以写作 $(x, 0) \rightarrow(f(x), g(x))$ 。我们亦可以在电路开头添加受控非门去产生 $x$ 的一个副本，并且其在计算过程中值不会发生改变。利用这些修改，电路可以写成
$$ \begin{equation*} (x, 0,0) \rightarrow(x, f(x), g(x)) \tag{3.7} \end{equation*} $$
式（3.7）对于表达可逆电路的行为是一种非常有用的方式，因为它允许使用称为还原计算的想法来消除无用比特，而在计算运行时间上只花费很少的成本。这一想法如下：假设我们从处于状态 $(x, 0,0, y)$ 的拥有四个寄存器的计算机开始，其中第二个寄存器用于存储计算结果，第三个寄存器用于提供计算工作空间，即无用比特 $g(x)$ 。稍后将描述第四寄存器的用途，并且我们假设它以任意的状态 $y$ 开始。
开始时和之前一样，通过运行计算 $f$ 的可逆电路得到状态 $(x, f(x), g(x), y)$ 。接着，使用受控非门将 $f(x)$ 按位地加到第四个寄存器上，得到状态 $(x, f(x), g(x), y \oplus f(x))$ 。注意到计算 $f(x)$的过程是可逆的，并且不会影响第四个寄存器，故通过运行计算 $f$ 的逆电路我们将得到状态 $(x, 0,0, y \oplus f(x))$ 。通常我们在函数计算的描述中省略辅助位的 0 ，并将电路的过程写为
$$ \begin{equation*} (x, y) \rightarrow(x, y \oplus f(x)) \tag{3.8} \end{equation*} $$
一般地，我们将这种修改后的计算 $f$ 的电路称为计算 $f$ 的可逆电路，尽管原则上还有许多其他可逆电路可用于计算 $f$ 。
进行可逆计算涉及哪些资源上的开销？为了分析这个问题，我们需要计算可逆电路中所需的额外辅助比特的数量，并将所需电路门的数目与经典模型进行比较。应该明确的是，可逆电路中门的数量与不可逆电路中门的数量在差一个常数因子的意义下是相同的，该常数因子涉及模拟不可逆电路的单个元件所需的 Fredkin 门的数量和另一个因子 2 用于完成计算还原，以及可逆计算中使用的额外受控非门操作的开销与电路中涉及的比特数呈线性关系。类似地，所需的辅助比特数最多与不可逆电路中的逻辑门数成线性关系，因为不可逆电路中的每个元素可以使用常数个辅助比特来模拟。因此无论使用可逆或不可逆的计算模型，自然的复杂性类（例如 P 和 NP）都是没有区别的。对于像 PSPACE 这样更复杂的复杂性类，情况并不是那么明确；其中一些微妙的细节讨论请参阅问题 3.9 和＂背景资料与延伸阅读＂。
习题3.31（可逆半加器）构造一个可逆电路，它以 $(x, y)$ 作为输人，输出 $(x, y, c, x \oplus y)$ ，其中 $c$ 是 $x$ 和 $y$ 相加后的进位比特。
Fredkin 门及其在台球计算机上的实现为可逆计算提供了一个美妙的例子。还有另外一个可逆逻辑门 Toffoli 门，它对于经典计算也是通用的。尽管 Toffoli 门在台球计算机上没有像 Fredkin门那么优雅和简洁的实现，但它在量子计算的研究中将更有用。我们已经在 1.4.1 节中遇到过 Toffoli 门，但为了方便起见我们在这里回顾它的属性。
Toffoli 门有三个输人比特 $a, b$ 和 $c$ 。 $a$ 和 $b$ 被称为第一和第二控制位，而 $c$ 是目标位。该门保持两个控制位不变，如果两个控制位都是 1 则翻转目标位，否则目标位也不变。Toffoli 门的真值表和电路表示如图 3－17 所示。
| 输入 | 输出 | ||||
|---|---|---|---|---|---|
| $a$ | $b$ | $c$ | $a^{\prime}$ | $b^{\prime}$ | $c^{\prime}$ |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
图 3－17 Toffoli 门的真值表和电路表示
如何使用 Toffoli 门进行通用计算？假设我们希望计算比特 $a$ 和比特 $b$ 的与非。为了使用 Toffoli 门执行此操作，我们输入 $a$ 和 $b$ 作为控制位，并将初始置为 1 的辅助位发送到目标位，如图 3－18 所示。在目标位上的输出即为 $a$ 和 $b$ 的与非。正如我们对 Fredkin 门的研究所预期的那样，与非门的 Toffoli 门模拟需要使用特殊的辅助比特作为输人，并且模拟过程会输出一些无用比特。
图 3－18 通过 Toffoli 门实现与非门。顶端的两个比特代表了与非门的输人，第三个比特作为辅助比特，初始时置为 1 。与非门的输出在第三个比特上
Toffoli 门还可以被用来实现扇出操作：第一个控制位作为辅助比特初始时置为 1 ，将 $a$ 赋值给第二个控制位，则最后输出 $1, a, a$ 。详见图 3－19。之前我们已经讲过与非门和扇出门合在一起构成一组通用门，因此我们可以得出结论，任一电路可以被一个只包含 Toffoli 门和辅助比特的可逆电路高效模拟。可以使用与 Toffoli 门相同的方法实现诸如还原计算之类的有用的附加技术。
图 3－19 通过 Toffoli 门实现扇出门。Toffoli 门的第二个比特作为扇出门的输人，其它两个比特为处于标准态的辅助比特。第二和第三个比特的结果可以作为扇出门的输出
我们对可逆计算感兴趣的动机是我们希望了解计算所需要的能量。很明显，无噪声的台球计算模型不需要能量来运行；那么基于 Toffoli 门的模型呢？这只能通过检查用于计算 Toffoli 门的特定模型来确定。在第 7 章中，我们研究了几种这样的方案，事实证明，Toffoli 门可以以不需要能量消耗的方式来实现。
关于计算可以在没有能量消耗的情况下完成的想法存在一个重要的隐患。正如我们前面提到的，台球计算模型对噪声非常敏感，许多其他可逆计算模型也是如此。为了抵消噪声的影响，需要进行某种形式的纠错。这种纠错通常涉及系统在测量上的表现，以确定系统是否按预期运行，
或者是否发生了错误。由于计算机的存储器容量是有限的，那些用来存储错误校正中的测量结果的比特最终必须被擦除，以便为新的测量结果腾出空间。根据兰道尔原理，这种消除带来了相关的能量消耗，在统计计算的总能量消耗时必须考虑这些损失。我们在 12.4.4 节中更详细地分析了与误差校正相关的能量消耗。
我们可以从可逆计算的研究中得出什么结论？有三个关键的想法。首先，可逆性源于保持追踪每一比特的信息；只有在信息丢失或删除时才会发生不可逆的结果。其次，通过可逆地进行计算，我们消除了计算期间的能量消耗。原则上，所有计算都可以用零能耗完成。第三，可以有效地完成可逆计算，而不产生其值取决于计算输人的无用比特。也就是说，如果存在计算函数 $f$ 的不可逆电路，则通过具有功能 $(x, y) \rightarrow(x, y \oplus f(x))$ 的可逆电路能够有效地模拟该电路。
这些结果对物理学，计算机科学以及量子计算和量子信息的影响是什么？从一位关心散热性的物理学家或硬件工程师的角度来看，好消息是，原则上可以通过使计算可逆而使其无能量消耗，尽管实际上维持系统的稳定性需要耗散能量以免受噪声干扰。在更为基础的层面上，可逆计算的思想也导致了基础物理学中一个有着百年历史的问题的解决，这就是著名的麦克斯韦妖问题。专题 3.5 概述了这个问题及其解答的故事。从计算机科学家的角度来看，可逆计算验证了计算模型中不可逆元素的作用，例如图灵机（因为是否使用它们所得到的模型是多项式等价的）。此外，由于物理世界从根本上是可逆的，人们可以争辩说，基于可逆计算模型的复杂性类比基于不可逆模型的复杂性类更自然，问题 3.9 和＂背景资料与延伸阅读＂中重新讨论了这一点。从量子计算和量子信息的角度来看，可逆计算非常重要。为了利用量子计算的全部功能，量子计算中的任何经典子程序必须可逆地执行，而且不能产生依赖于经典输入的冗余比特。
习题3.32（Fredkin 门和 Toffoli 门的相互模拟）模拟 Toffoli 门最少需要多少个 Fredkin 门？模拟 Fredkin 门最少需要多少个 Toffoli 门？
像本章这样的一个简短介绍中，不可能涵盖计算机科学这样丰富的领域的所有伟大构想。我们希望向读者传达一些计算机科学家的思考方式，介绍一些基本概念，及与之相关的基础词汇表，这些对理解何谓＂计算＂至关重要。作为这一章的总结，我们简要的介绍一些更一般的问题，以便为如何将量子计算和量子信息置于整个计算机科学的图景中提供一些观点。
我们将围绕图灵机计算模型进行讨论。一些非常规的计算模型，例如大规模并行计算机，DNA计算机和模拟计算机，它们的计算能力较之标准图灵机计算模型（隐含的，较之量子计算模型）如何？我们从并行计算架构开始。绝大多数现有的计算机都是串行计算机，即同一时间在中央处理单元中只执行一条指令。与之相反，并行计算机允许同一时间执行多条指令，从而大大节省了实现某些应用所需的时间和金钱。尽管如此，相较于标准图灵机并行处理并不能带来效率上的根本性优势。因为图灵机可以在多项式的物理资源下（即在使用多项式的时间和空间的条件下）模拟并行计算机。并行计算在运行时间上的优势与其需要使用更多空间的劣势相抵消，因而在模型的计算能力并无本质的提升。
一个有趣的大规模并行计算机的实例是一种被称为 DNA 计算的技术。一条 DNA（脱氧核糖核酸）链是由四种核苷酸组成的分子序列（一种聚合物），不同的核苷酸由它们携带的不同碱基区分，分别用字母 A（腺嘌呤），C（胞嘧啶），G（鸟嘌呤）和 T（胸腺嘧啶）表示。如果相应的碱基对彼此形成互补（ A 匹配 T，G 匹配 C），在一定的条件下两条 DNA 链可以退火形成双链。链的两端也是不同的，必须适当地匹配。利用化学技术可以对 DNA 链执行一系列操作，例如增加以特定序列开始或结束的 DNA 链的占比（聚合酶链反应），将 DNA 链根据链长分开（凝胶电泳），通过改变温度和酸碱度将 DNA 双链拆解为单链，测定链上的碱基序列，在特定的位置将 DNA 链切开（使用限制酶），以及检测试管中是否存在特定序列的 DNA 链等。实际上，在一个具体的过程中以一种鲁棒的方式应用这些技术是很复杂的事情，但是它的基本思想由下述例子可窥一斑。
有向哈密顿路径问题是 3.2.2 节中介绍的哈密顿圈问题的一个简单但难度等价的变种，它的目标是判定 $N$ 个顶点的有向图 $G$ 中是否存在由给定顶点 $j_{1}$ 到顶点 $j_{N}$ 的哈密顿道路——即一条经过每个顶点恰好一次，且遵循图中每条边的方向的有向路径。该问题可以使用 DNA 计算机通过以下五步解决，其中 $x_{j}$ 是一组特别选取的互异的碱基序列（ $\bar{x}_{j}$ 为 $x_{j}$ 的补链），DNA 序列 $x_{i} x_{j}$编码图中的边，而 $\bar{x}_{j} \bar{x}_{j}$ 编码图中的顶点。（1）通过组合所有可能的顶点和边的 DNA 链的混合物并等待这些链退火反应，在图 $G$ 中生成随机路径；（2）通过放大以 $\bar{x}_{j_{1}}$ 开头并以 $\bar{x}_{j_{N}}$ 结尾的双链，仅保留那些起始于 $j_{1}$ 而终止于 $j_{N}$ 的路径；（3）通过对剩下的链作链长分离，仅留下长度为 $N$ 的路径；（4）通过将 DNA 拆分为单链，并将这些单链依次与表示每个顶点的所有单链进行退火，保留那些被退火的链，即通过筛选保留那些经过图中所有顶点至少一次的路径；（5）检查经过前四步的筛选之后是否有剩下的 DNA 链，如果有则存在哈密顿道路，否则不存在。为了以足够高的概率保证结果的正确性，$x_{j}$ 需要包含许多（约 30 个）碱基，并且在这个过程中需要使用数目庞大（约 $10^{14}$ 或者更多）的 DNA 链。
启发式方法可用于改进这一基本思想。当然，诸如此类的穷举搜索方法只有在可以有效地生成所有可能路径的情况下才起作用，因此所使用的分子数必然关于问题的规模（如上例中的顶点数）呈指数式增长。DNA 分子相对较小且易于合成，试管足以容纳大量的 DNA 组合，可以允许复杂性在一定范围内（最高到几十个节点）指数型地增长，但最终指数成本依然会限制这种方法的适用性。因此，虽然 DNA 计算为某些问题的解决提供了一种有吸引力且物理上可实现的计算模型，但它依旧是一种经典的计算技术，在原理上并没有超越图灵机的实质性改进。
模拟计算机提供了另一种执行计算的范式。当计算机用于计算的信息的物理表示基于连续的自由度而不是 0 和 1 时，称计算机是模拟的。例如温度计就可以被视为一种模拟计算机。使用电阻器，电容器和放大器的模拟电路也是一种模拟计算。诸如位置和电压之类的连续变量可以存储无限的信息量，因此这种机器在理论上可以利用无限的存储资源。但这仅仅是在没有噪声的理想情况是对的。有限量的噪声的存在将连续变量的可区分状态总数减少到了有限数量，从而将模拟计算机限制为仅能表示有限量的信息。在实践中，噪声使得模拟计算机的能力不比传统数字计算机以及图灵机更强大。人们可能会怀疑量子计算机只是一种特殊的模拟计算机，因为它使用连续参数描述量子比特状态；然而，事实证明，噪声对量子计算机的影响可以有效地数字化。因此，正如我们将在第 10 章中看到的那样，即使存在有限量的噪声，量子计算的优势仍然存在。
噪声对数字计算机产生了怎样的影响？在计算机的早期，噪声对于计算机来说是一个非常现实的问题。在一些原始计算机中，真空管每隔几分钟就会发生故障。即使在今天，噪声的影响也是诸如调制解调器和硬盘驱动器之类设备需要面对的重要问题。我们付出了相当大的努力来使用不可靠的组件来构建可靠的计算机。冯•诺依曼证明，该问题只需额外的多项式量级的计算资源就可以被解决。然而具有讽刺意味的是，现代计算机并没有用到这些结果，因为现代计算机的组件非常可靠。在现代电子组件中，故障率可以被控制到 $10^{-17}$ 甚至更低。由于这个原因，硬件错误很少发生，以至于不值得设计额外的机制来对这种错误进行防护。但另一方面，我们会发现量子计算机是非常精密的机器，可能需要大量应用纠错技术。
不同的体系结构可能会改变噪声的影响。例如，如果忽略噪声的影响，那么改变计算机体系结构使得多指令可以并行执行，可能并不会改变完成任务所需要的操作数量。然而，并行系统实质上会对噪声更鲁棒性，因为在这种架构下噪声的影响具有较少的时间累积。因此在实际分析中，算法的并行版本可能比串行实现具有一些实质性的优势。体系结构设计是经典计算机设计中一个被深人研究的领域。对于量子计算机而言，几乎没有任何相似的研究领域被发展出来，而对噪声的研究已经为未来的量子计算机体系结构提出了一些理想的特性，例如高度并行化。
第四种计算模型是分布式计算，即利用两个或更多个空间上分离的计算单元解决计算问题。显然，这种模型的计算能力并不强于图灵机模型，因为它可以被图灵机有效地模拟。然而，分布式计算衍生出了一个有趣的新的资源挑战：当计算单元之间的通信成本很高时，如何更好地利用多个计算单元。随着计算机通过高速网络连接在一起，这个问题变得特别有意义；虽然网络上所有计算机的总计算能力可能非常大，但是这种潜力往往很难被利用。很多有趣的问题不容易划分为若干个可以单独解决的子问题，经常需要在不同计算子系统之间的进行全局通信以交换中间结果或同步状态。在研究如何量化解决问题的通信要求的成本的过程中，衍生出一个专门的研究领域——通信复杂性。而当量子资源可用并且可以在分布式计算机之间交换时，通信成本有时会大幅降低。
在这些结论性的思想中，甚至在这整本书中一个反复出现的主题是，尽管计算机科学传统上不受物理限制，但物理定律最终不仅对计算机的实现方式，还对它们究竟能解决哪些问题产生了巨大的影响。作为计算问题的一种物理上的合理替代模型，量子计算和量子信息的成功紧扣了计算机科学的宗旨，并将计算机科学的概念推向物理学的最前沿。本书其余部分的任务是将来自这些不同领域的想法融合在一起，并为取得的结果而感到欣喜！
热力学定律决定了物理系统在热力学平衡下可以完成的工作量。在这些定律中，热力学第二定律指出封闭系统中的嫡永远不会减少。1871 年，詹姆斯•克拉克•麦克斯韦（James Clerk Maxwell）提出存在一台明显违反该定律的机器。他设想存在一个微型的小＂恶魔＂，如下图所示，它可以通过将快速分子和慢速分子分离到气瓶的两边来减少最开始处于平衡状态的气瓶的熵。这个恶魔将坐在中间隔板的一扇小门上，当快速分子从左侧接近时，恶魔会打开一扇门，让分子通过，然后将门关闭。通过将上述行为重复多次可以降低气瓶的总嫡，这
明显违反了热力学第二定律。
对麦克斯韦妖悖论的解决基于如下事实，为了确定分子的速度，恶魔必须对在两个分区之间移动的分子进行测量。测量结果必须存储在恶魔的存储器中，而任何存储都是有限的，恶魔最终必须开始从其存储中擦除信息，以便为新的测量结果留出空间。根据兰道尔的理论，这种擦除信息的行为增加了恶魔－气缸－环境这一组合系统的总摘。事实上，一个完整的分析表明，根据兰道尔原理组合系统因这种擦除信息的行为所增加的摘不少于组合系统因恶魔的行为而减少的摘，从而确保了整个系统遵循热力学第二定律。
问题3.1（Minsky 机）一台 Minsky 机由一组寄存器的有限集合 $r_{1}, r_{2}, \cdots, r_{k}$ ，和一段程序组成，其中每个寄存器均可以存储一个任意非负整数，而程序由如下两种类型的指令组成。第一种类型的指令形如：
含义是在程序的 $m$ 位置将寄存器 $r_{j}$ 加一，并将程序移动到点 $n$ 位置。第二种类型的指令形如：
表示如当前处于位置 $m$ 且寄存器 $r_{j}$ 中的值为正数，则将寄存器 $r_{j}$ 减一并将位置移动到点 $n$ ；如寄存器 $r_{j}$ 中的值为零，则不改变 $r_{j}$ 的中值并将当前位置移动到点 $p_{\circ}$ 一段 Minsky 机的程序由上述两种指令构成，形如：
程序的起始点和所有可能的终止点通常标记为零。该程序获取寄存器 $r_{1}$ 的值并将它们加到寄存器 $r_{2}$ ，同时将 $r_{1}$ 减为零。
1.证明所有的（图灵）可计算函数均可由 Minsky 机计算，换言之，给定可计算函数 $f(\cdot)$ ，存在一台 Minsky 机的程序由寄存器状态 $(n, 0, \cdots, 0)$ 开始，以状态 $(f(n), 0, \cdots, 0)$ 为输出；
2.证明任何可以在 Minsky 机上计算的函数（可计算性如上一问中所定义），都可以在图灵机上计算。
问题 3.2 （向量游戏）一个向量游戏由一个包含相同维度，整数分量的有限向量列表所确定。游戏由一个非负整数分量向量 $x$ 开始，从向量列表中找到第一个满足如下条件的向量 $v: x+v$的每一个分量都是非负的，并将该向量加到 $x$ 上，重复该过程直至找不到这样的向量。证明对于任何可计算函数 $f(n)$ ，存在一个向量游戏满足当游戏从向量 $(n, 0, \cdots, 0)$ 开始时，最后会得到向量 $(f(n), 0, \cdots, 0)$ 。（提示：证明任意 $k$ 寄存器的 Minsky 机均可由 $k+2$ 维的向量游戏模拟。） 问题3.3（Fractran）一个 Fractran 程序由一列正有理数 $q_{1}, q_{2}, \cdots, q_{n}$ 定义。一个 Fractran 程序通过如下过程作用在一个正整数 $m$ 上：找到第一个使得 $q_{i} m$ 为整数的有理数 $q_{i}$ ，并将 $m$ 替换为 $q_{i} m_{\circ}$ 。给定初始的正整数 $m$ ，重复上述操作直至找不到能使 $q_{i} m$ 为整数的有理数 $q_{i}$ ，过程停止。证明对于任意的可计算函数 $f(\cdot)$ ，存在一个 Fractran程序使得从 $2^{n}$ 开始，最后会得到 $2^{f(n)}$ 且过程中不会出现任何其他的 2 的幂。（提示：利于前面问题的结论。） 问题3.4（动力系统的不可判定性）Fractran 程序本质上是一个非常简单的，由正整数到正整数的动力系统。证明不存在算法可以判定动力系统是否会达到1。 问题3.5（两比特可逆逻辑的非通用性）假设我们正在尝试仅使用一比特和两比特可逆逻辑门和辅助比特来构建电路，证明存在布尔函数无法以这种方式来计算。进一步证明即使允许使用辅助比特，仅用一比特和两比特的可逆门也无法模拟 Toffoli 门。
问题3.6（近似 TSP 问题的难解性）假设存在 TSP 问题的近似算法保证可以以 $r$ 的近似比计算出 $n$ 个城市之间的最短遍历回路，其中 $r \geqslant 1$ 。设 $G=(V, E)$ 为任意的 $n$ 点顶点的图，通过如下步骤定义 TSP 问题的一个实例：以 $V$ 中的顶点作为城市，对于其中任意两个城市，如果这两个城市所对应的点在图 $G$ 中相邻则令这两个城市之间的距离为 1 ，否则这两个城市之间的距离为 $\lceil r\rceil|V|+1$ 。证明如果将前述近似算法应用到该实例上，那么当 $G$ 中存在哈密顿回路时，该算法会返回该回路，否则算法返回的回路长度大于 $\lceil r\rceil|V|$ 。根据哈密顿回路问题的 NP 完全性可以推知，除非 $\mathrm{P}=\mathrm{NP}$ ，否则不存在这样的近似算法。 问题3.7（可逆图灵机） 1.如何构造一个可逆的图灵机，使得它可以计算在普通图灵机上可计算的函数类。（提示：尝试使用多带图灵机构造。） 2.如普通的单带图灵机计算函数 $f(x)$ 需要 $t(x)$ 的时间和 $s(x)$ 的空间，请给出上一问中所构造的可逆图灵机计算 $f(x)$ 所需要的空间和时间。
问题3.8（找到难于计算的函数类——研究型问题）找到一个 $n$ 输人的自然函数类，需要超过多项式个布尔门来计算。 问题3.9（可逆 PSPACE＝PSPACE）可以证明 QSAT 问题，即＂量词化可满足性问题＂是 PSPACE 完全的。换言之，任何 PSPACE 类中的语言都可以在多项式时间内被归约到 QSAT 问题。语言 QSAT 包含所有满足如下条件的布尔公式 $\varphi: \varphi$ 是包含 $n$ 个变量 $x_{1}, \cdots, x_{n}$ 的合取范式，且满足：
$$ \begin{align*} & \exists x_{1} \forall x_{2} \exists x_{3} \cdots \forall x_{n} \varphi \text { 成立, 当 } n \text { 为偶数时 } \tag{3.9}\\ & \exists x_{1} \forall x_{2} \exists x_{3} \cdots \exists x_{n} \varphi \text { 成立, 当 } n \text { 为奇数时 } \tag{3.10} \end{align*} $$
证明可逆图灵机可以在多项式空间内解决 QSAT 问题。因此，可以被计算机在多项式空间内使用可逆操作判定的语言类等于 PSPACE。
问题 3.10 （辅助比特和可逆计算效率）令 $p_{m}$ 为第 $m$ 个素数。构造如下可逆电路：对于正整数输人 $n$ 和 $m$（满足 $n > m$ ），输出乘积 $p_{n} p_{m}$ ，具体地，实现 $(m, n) \rightarrow\left(p_{m} p_{n}, g(m, n)\right)$ ，其中 $g(m, n)$ 是电路所用到的辅助比特的终态。估计该电路所用到的辅助比特的数量。证明如果存在一个计算上述问题的多项式（ $\log n$ 的多项式）规模的可逆电路，且该电路仅用到 $O(\log (\log n))$个辅助比特，那么分解两个素数的乘积问题在 P 类中。
计算机科学是一门包含众多有趣的子领域的宏大学科，我们不能寄希望于在有限的篇幅内完整的介绍它，但是可以借此机会向读者推荐一些人们普遍感兴趣的问题，以及一些关于特定主题的工作，这些主题在本书中均有所涉及，希望这些内容能对读者有所启发。
现代计算机科学可以追溯到 1936 年图灵那篇令人惊叹的论文［Tur36］。丘奇－图灵论题最早由丘奇于 1936 年提出 ${ }^{[C h u 36]}$ ，之后由图灵从不同的角度进行了更完整的讨论。而其他几位研究者几乎在同一时间用各自的方法给出了类似的结论。相关的学术贡献和研究历史的介绍详见 Davis的著作［Dav65］。对丘奇－图灵论题和不可判定性的质疑可以参阅 Hofstadter ${ }^{[H o f 79]}$ 和 Penrose ${ }^{[P e n 89]}$的著作。
关于算法设计的优秀书籍有很多，我们只介绍其中三本。首先，高德纳的经典丛书［Knu97， Knu98a，Knu98b］涵盖了计算机科学的大部分内容；其次，我们推荐 Cormen，Leiserson 和 Rivest不同凡响的作品［CLR90］，这本巨著囊括了关于算法设计各个领域的精心撰写的介绍；最后，推荐 Motwani 和 Raghavan 的著作［MR95］，这是一部对随机算法领域优秀的综述。
Cook ${ }^{[C o o 71]}$ 和 Karp ${ }^{[K a r 72]}$ 的论文对现代的计算复杂性理论产生了深远的影响。Levin ${ }^{[L e v 73]}$ 在俄国独立地提出了类似的理论，但不幸的是，他的贡献在很久之后才为西方世界所知。Garey 和 Johnson ${ }^{[G J 79]}$ 的经典著作也对该领域产生了巨大的影响。最近，Papadimitriou ${ }^{[P a p 94]}$ 撰写了一本出色的书，综述了许多计算复杂性理论的重要观点，本章的许多内容都基于此书。在本章中，我们只考虑了语言之间的一种归约方式，即多项式时间归约。实际上，语言之间还有许多其他归约方式。Ladner，Lynch 和 Selman ${ }^{[L L S 75]}$ 对这些概念进行了综述。对归约中的不同概念的研究后来发展成为一个被称为结构复杂性的研究领域，Balcázar，Diaz 和 Gabarró ${ }^{[8 D G 88 a, ~ B D G 88 b]}$ 对此进行了综述。
信息，能量消耗和计算之间的联系历史悠久。对这种联系的现代理解源于兰道尔 ${ }^{[L a n 61]}$ 于 1961年发表的一篇论文，其中首次提出了兰道尔原理。Szilard ${ }^{[\text {Szi29］}}$ 的一篇论文和冯•诺伊曼 ${ }^{[v o n 66]} 1949$年的一篇讲义（第 66 页）得出了与兰道尔原理相近的结论，但他们没有抓住擦除信息需要消耗能量这一本质。
可逆图灵机最早由 Lecerf ${ }^{[\text {Lec66］}}$ 提出，其后 Bennett ${ }^{[B e n 73]}$ 在他有影响力的独立工作中也提出了相同的概念。Fredkin 和 Toffoli ${ }^{[F 782]}$ 引入了可逆电路计算模型。两篇有趣的文献是 Barton 在 1978
年 5 月麻省理工学院 6.895 课程论文 ${ }^{[B a r 78]}$ 和 Ressler 在 1981 年的硕士论文 ${ }^{[R e s 81]}$ ，其中包含可逆 PDP－10 计算机的设计！今天，可逆逻辑在低功耗 CMOS 电路的实现中具有潜在的重要性 ${ }^{[Y K 95]}$ 。
麦克斯韦妖是一个迷人的主题，复杂而历史悠久。麦克斯韦于1871年提出了这一概念 ${ }^{[\mathrm{Max} 71]}$ 。 Szilard 于 1929 年发表了一篇关键论文 ${ }^{[\text {Szi29］}}$ ，该论文预言了麦克斯韦尔妖问题最终解决的许多细节。1965 年，费曼 ${ }^{[F L S 65 b]}$ 解决了麦克斯韦妖问题的一个特例。Bennett 在兰道尔结果 ${ }^{[L a n 61]}$ 的基础上，写了两篇关于这个主题的精彩论文 ${ }^{[B e n 82, ~ B e n 87]}$ ，从而解决了该问题。由 Leff 和 Rex 整理的论文集 ${ }^{[L R 90]}$ 介绍了麦克斯韦妖及＂除妖＂史。
DNA 计算是 Adleman 发明的，我们描述的有向哈密顿道路问题的解决方案最早由他提出 ${ }^{[A d 194]}$ 。 Lipton 还展示了如何利用该模型来解决 3SAT 问题以及电路可满足性问题 ${ }^{[L i p 95]}$ 。关于 DNA 计算，Adleman 在《科学美国人》杂志上发表了一篇综述性的文章 ${ }^{[\text {AdI98］}}$ ；如果读者希望深人的了解 DNA 计算的通用性，可以参阅 Winfree ${ }^{[\text {Win98］}}$ 的文章。想了解噪声环境下的可靠计算，Winograd和 Cowan ${ }^{[W C 67]}$ 的书是一个不错的选择，这个主题也将在本书第 10 章中再次讨论。由 Hennessey， Goldberg 和 Patterson 撰写的［HGP96］是一本介绍计算机体系结构的优秀教材。
问题 3.1 到 3.4 探讨了由 Minsky（在他关于自动计算机的杰出著作 ${ }^{[M i n 67]}$ 中）提出并由 Con－ way ${ }^{[C o n 72, C o n 86]}$ 发展的计算模型设计思路。Fractran 编程语言无疑是已知的最美妙和优雅的通用计算模型之一，如以下素数游戏（PRIMEGAME）所展示的 ${ }^{[C o n 86]}$ 。素数游戏定义为一列有理数：
$$ \frac{17}{91} ; \frac{78}{85} ; \frac{19}{51} ; \frac{23}{38} ; \frac{29}{33} ; \frac{77}{29} ; \frac{95}{23} ; \frac{77}{19} ; \frac{1}{17} ; \frac{11}{13} ; \frac{13}{11} ; \frac{15}{2} ; \frac{1}{7} ; \frac{55}{1} $$
令人惊讶的是，当素数游戏从 2 开始时，过程中出现的其余 2 的幂，即 $2^{2}, 2^{3}, 2^{5}, 2^{7}, 2^{11}, 2^{13}, \cdots$ ，恰好是 2 的素数次幂，且其指数对素数依序遍历。问题 3.9 是更一般的可逆计算的空间需求这一研究领域的一个特例，详见 Bennett ${ }^{[B e n 89]}$ 以及 Li，Tromp 和 Vitanyi ${ }^{[L V 96, ~ L T V 98]}$ 的论文。
（1）本书符号基本上与英文原版保持一致，仅为阅读方便对常数符号等按国标进行了改动。