前言

我们珍视但无法许诺自己能够达成这样的理想：我们对于“无用的知识”无拘无束的追求，将会在未来如同以往一样结出硕果。…… 一所能够解放人类灵魂的机构，无论其毕业生是否作出所谓“有用”的贡献，其正当性就已经得到保证。一首诗歌、一首交响曲、一幅画卷、一条数学真理、一个科学事实，它们自身就已经包含了大学、学院以及研究所科学研究中需要或者要求的所有正当性。 ——Abraham Flexner，《无用以为用》

我建议你尝试你力所能及最困难的课程，因为只有当你挑战自我的时候才能够学到最多的知识……另外，我觉得CS121这门课真的很难。 ——Mark Zukerberg，2005

这本书是针对本科生的计算理论入门课程。本课程的课程目标如下：

• 学生们能够了解，计算在任何自然或者人造的系统中都存在，不仅仅存在于硅基现代计算机当中；
• 类似地，我们要超越将计算理解为极其重要的“工具”的观念，进一步认识到——计算是描述自然、物理、数学甚至社会学概念的洞察工具；
• 学生们能够了解“普遍性”的观念以及编码和数据的对偶性观念；
• 学生们应该了解如何从数学上定义计算，并使用这样的工具去证明（有时仅仅是猜想）计算的下界以及不可能的结果。
• 学生们要了解一些在现代理论计算机科学中出人意料的结果和发现，包含NP完全性的普遍性、交互的力量、随机性以及去随机的力量、用计算“难度”保证优质的加密，以及量子计算的无限可能。

我希望通过上述课程，学生们能够认识到计算的能力与隐患。这是因为，在许多不同的背景下，例如宏定义和脚本等等看似“静态”和“有限制”的内容与形式，我们都需要讨论“计算”在其中表现出的性质。学生们应该能够理清计算证明的逻辑，包含归约的核心观点以及“自引用”的证明（例如对角化证明中，我们通过将其自身编码作为输入以导出矛盾）。学生们应该明白，某些问题是固有的难解决的，同时他们也应该能够在面对一个新问题的时候，识别其是否难以解决。尽管本书仅仅是短浅地涉猎密码学，学生们也应该了解我们在密码学中使用计算难度的目的。不论如何，本书不会局限于特定的技巧，而是要让学生们具有一种全新的思维——将计算本身视为独立的对象来审视与探究，并展示这种思维如何带来深远洞见与广泛应用。

我写作本书的目标是以最简单的方式阐明计算理论中的概念，并且尝试让规范的记号与模型的核心理念更加好理解而不是晦涩难懂。我同时尝试利用学生们在编程方面的经验，拉近学生们与计算理论之间的关系（至少让教学内容更加有趣！），因此我使用了（高度简化）的编程语言来描述我们的计算模型。话虽如此，本书并不假定你对于任何特定编程语言驾轻就熟，而只要求你对“编程”这一总体概念有基本的熟悉。我们常常使用编程中的一些比喻和习惯，偶尔会提及Python、C或者Lisp等具体语言，但即使对于这些语言不熟悉，学生们也能毫无障碍地理解相关描述。

本书中的证明，包含通用图灵机的存在性、有限值函数的电路可计算性、Cook-Levin定理以及其它许许多多的定理，通常都是构造性和算法性的，因为他们的最终目的都是将一个程序转换为另一个程序。尽管不看代码就阅读证明是完全可能的，我坚信保留代码资源，并且在各实际问题上实现它们并观察其表现对于学生具体地理解定理内容是更加有效的。为了达到这个目的，我们搭建了一个辅助的网站（仍在开发中）以允许学生们在我们定义的不同的计算模型上运行这些程序。与此同时，本网站也可以观看某些定理的构造性证明。

前言1 致学生们

这一本书可能相当具有挑战性，主要原因是这本书中将各种计算理论的观点和技术融合到了一起。其中一些技巧是比较难以掌握的，不论是通过对角线论证证明停机问题的不可判定性，还是在NP完全问题归约中使用的组合工具，抑或是分析概率算法，再或者是通过讨论对抗过程从而证明密码学基本构件的安全性。

阅读这本书的最佳方法是积极地去阅读笔记，所以说我建议你准备好你的笔。当你阅读这本书的时候，我鼓励你不时地停下来并思考如下地问题：

• 当我陈述一个定理的时候，停下来并用一点时间尝试在你阅读证明之前自己证明这个定理。在这短短五分钟的尝试以后，你将会为能更好地理解标准证明而感到惊喜。
• 当你在阅读定义的时候，一定要保证你完全理解了定义的含义，以及哪些自然的例子能够成为定义所描述的对象。此外，一定要去思考定义背后的动机，以及是否有其它自然的方式来形式化这些概念。
• 积极地注意你阅读过程中，脑中浮现出的问题，并且考虑他们是否在阅读文本的过程中得到了解答。

一个普遍的规则是，理解定义比理解定理更加重要，理解定理比理解证明更加重要。不论如何，在你证明定理之前，你一定要理解它到底陈述的是什么，一定要了解定理中对象所涉及的定义。不论证明如何复杂，我会提供证明定理的“证明想法”。你可以在第一次阅读的时候自由地跳过正式的证明，而单独把注意力放在“证明想法”上面。

本书包含了一部分代码片段，但这并不代表他们是编程文本。实际上，在阅读本书的时候，你不必知道如何进行编程。我们使用代码的原因，仅仅是为了更加精确地描述计算过程。实际的实现细节对于我们而言是不重要的，因此我们将会强调以更多考量换取代码可读性的重要性，例如错误处理、代码封装，等等，这些技巧对于我们实际的编程是非常重要的。

但是这些努力是否值得？

这并不是一本简单的书，你有理由思考自己为什么自己要花费这么多精力在学习这本书之上。一个对于计算理论课程的经典辩护是，你可能会在你未来的工作中遇到这些概念。你可能会遇到一个非常困难的问题，而后续你会意识到它是一个NP完全问题；又或者，你会在未来找到应用你所学到的正则表达式的地方。这可能是实话，但是这本书的主要功用并不是教给你任何实用的工具或者技能，而是给予你一种全新的思考方式：一种在计算问题出现时、穿破重重看似无关的设定识别它们的思想，一种建模计算任务和问题的思想，以及通过以上两个思想进行推理的能力。

无论你如何运用这本书，我都相信学习这本书是非常重要的。这是因为，它包含了许多非常优美且基本的概念。在本世纪，计算与信息扮演了能量和物质在上世纪的角色——作为我们理解世界的基石，而并不仅仅是作为我们科技和经济的工具。这本书将会让你简单了解这些理论背后的内容，并且希望能够激发各位读者进一步学习和了解更多知识的动力。

前言 2 致未来的授课教师们

这本书虽然是我为哈佛大学课程所作，但是我希望其它授课教师也认为它大有裨益。从某种意义上来讲，它与卡内基梅隆大学和麻省理工学院开设的“计算理论导论”和“伟大的想法”等课程的内容是类似的。

这本书所使用的教学方法与其它传统书籍（例如Hopcroft和Ullman于1969年出版的教材以及Sipser在1997年出版的教材）最显著的不同，在于本书将不会从有限自动机开始建立计算模型。相反，我们将会从布尔电路出发来建立这一切。我们相信，布尔电路才是计算理论中比自动机更加基本的内容。（甚至也是更加实用的！）更重要的是，布尔电路是许多只会在介绍现代理论计算机理论的课程中才会被提及的诸概念的前置概念。这些理论理论包括现代密码学、量子计算、去随机化理论、一些对于证明$\mathbf{P}\ne \mathbf{NP}$的尝试，等等等等。甚至，在某些并不必须使用布尔电路的情况下，布尔电路能够极大地简化这些问题（例如在证明Cook-Levin定理时）。

不仅如此，我认为以布尔电路而不是有限自动机作为起始，还有许多教学上的理由。布尔电路是更加自然的计算模型，其与硅基电路联系紧密，能够与学生们的实践直接产生关联。按理来说，有限值函数往往比无限值函数更容易掌握，因为我们完全可以将它的真值表直接写出。“任何一个有限值函数都可以被布尔函数计算”，这样的简单但是重要的定理可以作为课程的一个极好的起点。更进一步，许多计算理论中的观点，例如编码和数据之间对偶关系的观点、“普遍性”的观点等等，我们都可以从这一理论中体悟出来。

紧随布尔电路，我们将会进入图灵机的学习，并且证明一些重要的结果，例如通用图灵机的存在、停机问题的不可计算性以及Rice’s Theorem。我们将会在了解图灵机和不可判定性之后讨论自动机，并将其作为限制型计算模型的例子（这一类机器的停机问题可以被高效解决）。

尽管按照电路——图灵机——自动机的顺序来介绍并不是我们的初衷，这个顺序与这些模型的发现的时间顺序是恰好吻合的。布尔代数可以追溯到Boole和DeMorgan在19世纪40年代的工作（尽管布尔电路的严格定义由Shannon在90年之后才给出）。Alan Turing在20世纪30年代定义了我们现在所称呼的“图灵机”，而有限自动机在1943年才在McCulloch和Pitts的工作中被正式提出。并且，直到1959年Rabin和Scott发表了他们重要的工作以后，自动机才逐渐被人们所了解。

更重要的是，尽管诸如有限自动机、正则表达式以及上下文无关语法在工程中非常重要，这些模型能够得到重用（不论是用于语法解析、分析生命周期和安全性还是用于软件定义路由表）绝大部分都要归因于他们是可控制的模型，我们可以轻易地通过它们来回答一些语义上的问题。在学生了解了通用计算模型的语义性质的不可判定性，它们可能会对这些实际应用上的想法感到叹为观止。

从电路入门使得我们证明Cook-Levin Theorem非常方便。事实上，我们的证明可以被一些Python程序完成。通过将这个证明与标准的归约结合，学生们能够直观地欣赏计算理论中的问题是如何被转化为图中独立集的存在性问题的。

这里，我们列举出一些与过往文献的不同：

1. 为了衡量时间复杂度，我们使用在算法课中使用过的标准的RAM机器模型（隐式的）而不是图灵机。尽管这两个模型毫无疑问是多项式等价的，且两个模型上复杂度类$\mathbf{P}$和$\mathbf{NP}$以及$\mathbf{EXP}$没有任何区别，我们的选择使得记号$O(n)$和$O(n^2)$之间的区别更加有意义。这样的选择使得这些更加细致的复杂度类型对应上学生们在算法课上学到的关于线性和二次时间的非正式定义（或者是对于需要他们手写代码的面试环节有所好处）（译者注：面试环节通常需要面试者在白板上手写代码，并给出时间复杂度分析）。

2. 我们使用“函数”而不是“语言”。这就是说，与其说“图灵机$M$判定语言$L\subseteq \{0,1{\}}^{\ast }$”，我们说它“计算了一个布尔函数$F:\{0,1{\}}^{\ast }\to \{0,1\}$”（译者注：$\{0,1{\}}^{\ast }$表示任意长度的二进制串，或者说0-1串）。“语言”这一术语兴起于Chomsky的1956年的工作，但是往往令人迷惑。“语言”相关的术语同时也使得讨论有关计算有多比特输出的函数的算法相关的概念非常的低效（包含一些非常基本的任务，例如讨论加法、乘法，等等）。但是，使用函数而不是语言意味着我们必须格外警惕学生可能会把“计算任务的规范”（函数）和“该任务的实现”（程序）搞混。另一方面，我们必须重复向学生强调和并训练他们要牢记这一点，无论使用何种记号。但是与此同时，本书同样会时不时提及“语言”相关的术语，以便于学生在课外查找相关资料。

上面教学大纲对于有限自动机和上下文无关语言的减免使得授课教师们能够讲授更多在现代理论课程之前所需要了解的知识。它们包括：随机性和计算，程序和证明之间的交互（包含哥德尔不完备定理、交互式证明系统、甚至包含一些Lambda演算、Curry-Howard同构）、密码学以及量子计算。

这本书提供了足以进行自学的细节。为了达到这个目的，每一个章节的开头都会列举这个章节的学习目标，末尾则会进行总结和回顾，行文之间穿插着“停顿框”以鼓励学生们停下来并求解一个问题或者检查他们是否在继续学习之前完全明白了前文所述的定义。

“第0章”的第五节提供了本书的一个“地图”，概括性地描述了不同章节的大概内容，同时还阐述了他们之间的依赖关系。这对于课程的规划是非常有益的。

致谢

这段文字正在持续更新，我收到了许多人的反馈，对此我深怀感激。Salil Vadhan 与我共同教授了这门课程的最初版本，在此过程中给予了我大量宝贵的反馈与洞见。Michele Amoretti 和 Marika Swanberg 仔细审阅了本书的若干章节，并提供了极其详尽且有益的评论。Dave Evans 和 Richard Xu 提交了许多 pull request，修正错误并改进措辞。感谢 Anil Ada、Venkat Guruswami 和 Ryan O’Donnell 分享他们在教授 CMU 15-251 时的经验与建议。感谢 Adam Hesterberg 和 Madhu Sudan 就使用本书教授 CS 121 的经验提出意见。Kunal Marwaha 提供了诸多评论，并在本书的技术制作方面给予了极大帮助。

感谢所有通过 GitHub 仓库 https://github.com/boazbk/tcs 发送评论、报告错别字或提交 issue 与 pull request 的人。特别感谢以下人士的宝贵反馈：Scott Aaronson、Michele Amoretti、Aadi Bajpai、Marguerite Basta、Anindya Basu、Sam Benkelman、Jarosław Błasiok、Emily Chan、Christy Cheng、Michelle Chiang、Daniel Chiu、Chi-Ning Chou、Michael Colavita、Brenna Courtney、Rodrigo Daboin Sanchez、Robert Darley Waddilove、Anlan Du、Juan Esteller、David Evans、Michael Fine、Simon Fischer、Leor Fishman、Zaymon Foulds-Cook、William Fu、Kent Furuie、Piotr Galuszka、Carolyn Ge、Jason Giroux、Mark Goldstein、Alexander Golovnev、Sayan Goswami、Maxwell Grozovsky、Michael Haak、Rebecca Hao、Lucia Hoerr、Joosep Hook、Austin Houck、Thomas Huet、Emily Jia、Serdar Kaçka、Chan Kang、Nina Katz-Christy、Vidak Kazic、Joe Kerrigan、Eddie Kohler、Estefania Lahera、Allison Lee、Benjamin Lee、Ondřej Lengál、Raymond Lin、Emma Ling、Alex Lombardi、Lisa Lu、Kai Ma、Aditya Mahadevan、Kunal Marwaha、Christian May、Josh Mehr、Jacob Meyerson、Leon Mlodzian、George Moe、Todd Morrill、Glenn Moss、Haley Mulligan、Hamish Nicholson、Owen Niles、Sandip Nirmel、Sebastian Oberhoff、Thomas Orton、Joshua Pan、Pablo Parrilo、Juan Perdomo、Banks Pickett、Aaron Sachs、Abdelrhman Saleh、Brian Sapozhnikov、Anthony Scemama、Peter Schäfer、Josh Seides、Alaisha Sharma、Nathan Sheely、Haneul Shin、Noah Singer、Matthew Smedberg、Miguel Solano、Hikari Sorensen、David Steurer、Alec Sun、Amol Surati、Everett Sussman、Marika Swanberg、Garrett Tanzer、Eric Thomas、Sarah Turnill、Salil Vadhan、Patrick Watts、Jonah Weissman、Ryan Williams、Licheng Xu、Richard Xu、Wanqian Yang、Elizabeth Yeoh-Wang、Josh Zelinsky、Fred Zhang、Grace Zhang、Alex Zhao 与 Jessica Zhu。 在本书的排版与制作过程中，我使用了许多开源软件包，对此我满怀感激。特别感谢 Donald Knuth 与 Leslie Lamport 创造了 LaTeX，以及 John MacFarlane 开发了 Pandoc。David Steurer 编写了最初用于生成此文本的脚本。当前版本使用了 Sergio Correia 的 panflute。LaTeX 与 HTML 模板源自 Tufte LaTeX、Gitbook 和 Bookdown。感谢 Amy Hendrickson 提供的 LaTeX 咨询。Juan Esteller 与 Gabe Montague 最初用 OCaml 与 JavaScript 实现了 NAND* 编程语言。我使用 Jupyter 项目编写了补充代码片段。

最后，我要感谢我的家人：我的妻子 Ravit，以及我的孩子 Alma 与 Goren。撰写本书（以及相应的课程）占用了我大量时间，以至于 Alma 在她的五年级作文中写道：“大学不应当逼迫教授过度工作。”遗憾的是，我所能展示的成果，似乎只是 600 页极度枯燥的数学文字。

格式统一教程: 标题

• 原文存在一些对章节标题id的引用, 如([如](#templatetitle)). 这些统一替换成对章节文件名的引用([引用](chapter_x.md))

学习目标

• 此处填写学习目标
• 一些目标
• 二些目标
• 三些目标

目录

• x.1 小节: 右侧花括号添加 #id 即可用于引用
  • x.1.1 依然是小节名示例. 小节名总是可以添加id.
• x.2 小节: 各类环境使用方式汇总
  • x.2.1 admonish
• 习题
• 杂记
  • 未完成章节中的引用:

以下是教程正文.

• 每一章以一些插图引入比较合适, 如下图, 然后再写正文前的引子.

• 使用<span>即可添加能够超链接的ID (源码:[引用](#templateimage)), 点击即可跳转.

• 原文中用斜体强调的词, 在译文中统一用加粗, 如:

译作

• 对某一章的引用可以直接引.md: 例如本章 ([本章](chapter_x.md)), 对章节的引用则使用html id语法糖, 如下方x.1小节([x.1小节](#templatesection))所示.

x.1 小节: 右侧花括号添加 #id 即可用于引用

• 渲染时看不到上面说的花括号, 实际语句是: ## x.1 小节: 右侧花括号添加 #id 即可用于引用 { #templatesection }

• quote 可以带标题, 遵照原文即可. 当原文需要引用的时候, 就使用 quote.

• 代码块照常写即可.

# 使用 Python 的 sqrt 函数来计算平方根
def solve_eq(b, c):
    # 根据 al-Khwarizmi 的方法求解 x^2 + b*x = c
    blablabla()
# 测试: 求解 x^2 + 10*x = 39
print(solve_eq(10, 39))

• 出现在公式中的函数名全部应该用 \text 框起, 如 $\text{XOR}$($\text{XOR}$). 如果发现某个名字经常出现, 应该将其添加进./makros.txt. 如与($\text{AND}),$ 或($\text{OR}),$ 非($\text{NOT}).$ ($\AND, \OR, \NOT$)

• example 环境的示例. 注意其中嵌套了代码, 所以使用了~~~ 取代 ```. admonish的title中如果需要使用公式, 反斜杠需要重复三次. 例如下方的标题就出现了 $\\\text{MAJ}$.

def MAJ(X[0],X[1],X[2]):
    firstpair  = AND(X[0],X[1])
    secondpair = AND(X[1],X[2])
    thirdpair  = AND(X[0],X[2])
    temp       = OR(secondpair,thirdpair)
    return OR(firstpair,temp)

• 公式的引用: 在行间公式中添加 [{numeq}]{id}, 例如: $$\text{foo}\to \text{bar}\text{\hspace{1em}(1)}$$ 然后就可以直接引用: (1) ([{eqref: templatenumeq}])(为防止替换, 这里最外层的花括号替换成了方括号.)

x.1.1 依然是小节名示例. 小节名总是可以添加id.

• 所有 preprocessor numthm 引入的定理/例子/命题环境都需要套一个 admonish quote, 以和正文分隔开. book.toml中可以自定义这些环境. 已经定义了一些“常用缩写+c“为名的中文环境. 例如:

• numthm 的引用方式: 引理 1 ([{ref: templatelem}]) (为防止替换, 这里最外层的花括号替换成了方括号.)

• 小练习对应的 admonish solution 以及证明对应的 admonish proof 应该是 collapsible 的. 如:

• 原文的 pause 也有对应的 admonish:

• 算法的写法, 以下是一个例子:

当然, 与图片一样, 也可以使用llm帮助转换.

依照示例, 将以下格式的算法转换为tex格式:
Input: $a,b \in \{0,1\}.$
Output: $XOR(a,b)$

$w1 \leftarrow AND(a,b)$

$w2 \leftarrow NOT(w1)$

$w3 \leftarrow OR(a,b)$

return $AND(w2,w3)$
转换为
$
  \begin{array}{l}
  \mathbf{Input:}\ a,b \in \{0,1\} \\
  \mathbf{Output:}\ \XOR(a,b) \\
  \hline
  \mathbf{Step 1:}\ w_1 \leftarrow \AND(a,b) \\
  \mathbf{Step 2:}\ w_2 \leftarrow \NOT(w_1) \\
  \mathbf{Step 3:}\ w_3 \leftarrow\OR(a,b) \\
  \mathbf{Step 4: return}\ \AND(w_2,w_3)
  \end{array}
$
我将提供其它类似格式的算法输入.

• 脚注的例子 ¹ ([{footnote: 这是一条脚注}]). 最外层的方括号替换为花括号, 文中出现脚注时需要使用.

• 正文结束后, 用 admonish hint 写回顾

x.2 小节: 各类环境使用方式汇总

x.2.1 admonish

• 插入图片: 用pic环境框起, 再付一个numthm的pic编号环境. 源码:

```admonish pic id = '图片id'
![图片alt](图片地址)
    <-- 这里的空行不能省
[{pic}] 图片描述    <-- 外层花括号改为方括号, 和描述之间的空格不能省
```

效果如下, 引用可直接使用pic id:

插入图片的格式可以设计prompt交给llm处理. 下面给一个例子

请根据以下例子转换插入图片的格式:
![1959 至 1965 年间集成电路中的晶体管数量，并预测指数级增长至少能持续十年。取自戈登·摩尔 1965 年的文章 *Cramming More Components onto Integrated Circuits*。](./images/chapter3/gordon_moore.png){#moorefig .margin}  
转换为
```admonish pic id = "moorefig"
![moorefig](./images/chapter3/gordon_moore.png)

[{pic}] 1959 至 1965 年间集成电路中的晶体管数量，并预测指数级增长至少能持续十年。取自戈登·摩尔 1965 年的文章 *Cramming More Components onto Integrated Circuits*。
```
我将提供其它相同格式的代码, 输出请装在代码块内: 要再套一层代码块, 而不是使用已有的.

• 原文出现的 Big Idea(重要启示):

习题

• 习题的专有 numthm 环境是 proc. 例如:

• 依然可以先翻译习题(和标题), 再用llm调整格式, 以下是可用的prompt.

改变以下我输入的习题框的格式: 例如
::: {.exercise title="比较 $4$bit 数字" #comparenumbersex}

给出一个布尔电路（使用 $\AND/\OR/\NOT$ 门），该电路计算函数 $ \text{CMP}_8:\{0,1\}^8 \rightarrow \{0,1\}$，使得当且仅当由 $a_0a_1a_2a_3$ 表示的数大于由 $b_0b_1b_2b_3$ 表示的数时，$ \text{CMP}_8(a_0,a_1,a_2,a_3,b_0,b_1,b_2,b_3)=1$。
:::
改为

[{proc}]{comparenumbersex}[比较 $4$bit 数字]
给出一个布尔电路（使用 $\AND/\OR/\NOT$ 门），该电路计算函数 $ \text{CMP}_8:\{0,1\}^8 \rightarrow \{0,1\}$，使得当且仅当由 $a_0a_1a_2a_3$ 表示的数大于由 $b_0b_1b_2b_3$ 表示的数时，$ \text{CMP}_8(a_0,a_1,a_2,a_3,b_0,b_1,b_2,b_3)=1$。
接下来我将提供输入.

注意上面proc的方括号要改掉.

杂记

• 杂记需要修复对文献的引用. 使用 <a> 编写引用.

未完成章节中的引用:

以下是未完成的章节中的引用

未完成引用 1.

1: 这是一条脚注

• 引言
  • 学习目标
  • 0.1 整数的乘法: 一个算法示例
  • 0.2 扩展示例: 一种更快的乘法方法(可选)
  • 0.3 超越算术的算法
  • 0.4 论负面结果的重要性
  • 0.5 本书其余部分的路线图
    • 0.5.1 章节之间的依赖关系
  • 0.6 习题
  • 0.7 参考书目

引言

学习目标

• 介绍并激发对“计算“本身的研究兴趣, 而不局限于具体的实现方式.
• 了解算法(Algorithm)这一概念及其发展历程.
• 算法不只是一种工具, 更是一种思考和理解的方式.
• 领略大O分析法(Big-$O$ analysis)和高效算法设计中蕴含的惊人创造力.

位值数字系统(place-value number system)古巴比伦人最大的发明之一. 在位值数字系统中, 数字(number)被表示为一串数位(digit)序列, 其中每个数位的位置决定了其数值.

这与类似罗马数字的系统刚好相反, 在罗马数字中, 每个数位无论其在数字中的位置如何, 均有一个不变的值. 举个例子, 地球到月球的平均距离大概是259956罗马英里. 在标准罗马数字中, 这个数字的表示为:

MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMDCCCCLVI

使用罗马数字表示地球到太阳的距离需要大概100000个符号, 而我们需要一本50页的书来书写这一个数字!

对于那些习惯于像罗马数字那样以加法系统来思考数字的人来说, 诸如地球到月球距离的这种数字不仅仅是大—它们无法形容: 这些数字不能被有效地表达甚至是理解. 这也难怪第一个计算地球直径的埃拉托色尼(计算误差约为10%), 和第一个计算地球与月球之间距离的喜帕恰斯使用了古巴比伦的六十进制位值数字系统, 而不是使用罗马数字系统.

0.1 整数的乘法: 一个算法示例

在计算机科学的语言中, 这种用于表示数字的位值系统是一种数据结构(data structure), 数据结构是一组用于将对象表示为符号的指令或“配方“. 而算法(algorithm)则是在此类表示形式上执行操作的一组指令或“配方“. 数据结构与算法不仅催生了改变人类社会的惊人应用, 其重要性更远超实用价值. 比特(bit)、字符串(string)、图(graph), 乃至程序本身等计算机科学体系中的数据结构, 以及普适性、复制等概念, 不仅被广泛应用于实践领域, 更催生了一种全新的语言和审视世界的方式.

除了位值数字系统, 古巴比伦人还发明了我们在小学中都学过的加法和乘法的“标准算法“. 这些算法在漫长的历史中始终至关重要, 无论是使用算盘、莎草纸还是纸笔计算的人们均受惠于此, 但在计算机的时代, 除了折磨小学三年级学生之外, 这些算法是否还有存在的价值? 为了说明这些算法为何至今仍具有重要意义, 让我们将古巴比伦人的逐位相乘算法(即“小学乘法“)与通过重复相加实现的朴素乘法算法进行对比. 我们首先正式描述这两种算法, 详见算法 1和算法 2:

算法 6.1和算法 2均假定我们已经掌握了数字相加的方法, 而算法 2还假定我们能够将数字与10的幂相乘(毕竟这只相当于一次简单的移位). 假设$x$和$y$是两个$n=20$位的十进制整数(这大致相当于64位二进制数, 也是许多编程语言中常见的类型). 使用算法 6.1计算$x\cdot y$需要将$x$自身相加$y$次. 由于$y$有20位, 这意味着我们需要至少进行$10^{19}$次加法运算. 相比之下, 算法 2仅需$n^2$次移位和单位数字的乘法运算, 因此最多仅需$2n^2=800$次单位数字的操作. 为了理解这种差异, 假设一个小学生完成单位数字的操作需要2秒, 那么使用算法 2计算$x\cdot y$需要约1600秒(约半小时). 反之, 即使现代计算机的运算速度比人类快十亿倍以上, 若采用算法 6.1进行计算, 则需要$10^{20}/10^9=10^{11}$秒(超过3000年! )才能得到相同的结果.

计算机从未使算法过时. 恰恰相反, 随着人类测量、存储和传输数据的能力的大幅提升, 我们比以往更需要开发精密而高效的算法, 从而基于数据洪流做出更明智的决策. 我们也不难发现: 算法的概念在很大程度上独立于实际执行计算操作的设备. 无论是硅基芯片还是借助纸笔计算的小学三年级学生, 逐位相乘的算法都远胜于重复累加法.

理论计算机科学专注于研究算法和计算的内在属性—即那些独立于现有技术而存在的本质特征. 我们既探讨古巴比伦人早已思索过的问题(比如“什么是两数相乘的最优方法“), 也研究依赖前沿科技的课题(例如“能否利用量子纠缠效应实现更快速的因数分解“).

0.2 扩展示例: 一种更快的乘法方法(可选)

一旦你想到标准的逐位相乘乘法, 它似乎是“显然最优“的数字相乘方式. 1960年, 著名数学家安德雷·柯尔莫哥洛夫(Andrey Kolmogorov)在莫斯科国立大学组织了一场研讨会, 他在会上提出猜想: 任何两个$n$位数相乘的算法都需要执行与$n^2$成正比的基本操作次数(用第一章定义的大$O$符号表示为$\Omega (n^2)$次操作). 换言之, 柯尔莫哥洛夫认为在任何乘法算法中, 相乘的数字位数翻倍会导致所需基本操作次数变为四倍. 当时听众中有一位名叫阿纳托利·卡拉楚巴(Anatoly Karatsuba), 他在一周内就推翻了柯尔莫哥洛夫的猜想—他发现了一种仅需$C{n}^{1.6}$次操作($C$为常数)的算法. 随着$n$增大, 这个数字会远小于$n^2,$ 因此对于大数而言, 卡拉楚巴算法优于小学算法. (例如Python在处理1000比特及以上的数字时, 会从小学算法切换至卡拉楚巴算法. )虽然$O(n^{1.6})$与$O(n^2)$算法之间的差异有时在实践中至关重要(参见下文的0.3节), 但本书将基本忽略这类区别. 不过我们仍会在下文介绍卡拉楚巴算法, 因为它完美展现了算法往往出人意料的特性, 同时也体现了算法分析的重要性—这正是本书乃至整个理论计算机科学的核心所在.

卡拉楚巴算法基于一种两位数字之间的更快的相乘算法. 假设$x,y\in [100]=\{0,\dots ,99\}$是一对两位数字. 我们使用$\overline{x}$表示$x$的十位上数字, $\underline{x}$表示个位上的数字, 所以$x$可以表示为$x=10\overline{x}+\underline{x},$ $y$亦可写成$y=10\overline{y}+\underline{y},$ 这里$\overline{x},\underline{x},\overline{y},\underline{y}\in [10].$ 图 1展示了两位数字的小学乘法.

小学乘法的算法可以看作一个将两位数字相乘的任务转化为四个单位数字相乘的过程:

$$(10\overline{x}+\underline{x})\times (10\overline{y}+\underline{y})=100\overline{x}\overline{y}+10(\overline{x}\underline{y}+\underline{x}+\overline{y})+\underline{x}\underline{y}\text{\hspace{1em}(1)}$$

通常, 在小学算法中, 输入数字位数翻倍会导致操作次数变为原来的四倍, 从而形成$O(n^2)$时间复杂度的算法. 相比之下, 卡拉楚巴算法基于这样一个观察: 我们同样可以将(1)表示为:

$$(10\overline{x}+\underline{x})\times (10\overline{y}+\underline{y})=(100-10)\overline{x}\overline{y}+10\left[(\overline{x}+\underline{x})(\overline{y}+\underline{y})\right]-(10-1)\underline{x}\underline{y}$$

这将两位数字$x,y$的乘法简化为了以下三个更简单的乘积计算: $\overline{x}\overline{y}$、$\underline{x}\underline{y}$以及$(\overline{x}+\underline{x})(\overline{y}+\underline{y}).$ 通过递归地重复相同策略, 我们可以将两个$n$位数相乘的任务简化为三对$\lfloor n/2\rfloor +1$位数相乘的任务. 由于每当数字位数翻倍时, 操作次数会变为三倍, 因此当$n=2^l$时, 我们可以使用约$3^l=n^{{\log }_{2}3}\sim n^{1.585}$次操作完成乘法运算.

上述内容是卡拉楚巴算法背后的直观思想, 但尚不足以完整描述该算法. 一个算法的完整描述需要包含其操作步骤的精确说明以及算法分析: 即证明该算法确实能实现预设任务. 卡拉楚巴算法的具体操作步骤见算法 3, 其数学分析则包含在引理 1和引理 2中.

算法 3只是卡拉楚巴算法完整描述的一半, 另一半是算法的分析, 即证明(1)算法 3确实完成了乘法的计算以及(2)它确实使用了$O(n^{{\log }_{2}3})$步操作来完成计算. 我们首先从证明(1)开始:

卡拉楚巴算法远非乘法算法的终点. 20世纪60年代, 图姆(Toom)和库克(Cook)扩展了卡拉楚巴的思想, 提出了时间复杂度为$O(n{\log }_{}k(2k-1))$($k$为常数)的乘法算法. 1971年, 舍恩哈格(Schönhage)和施特拉森(Strassen)利用快速傅里叶变换实现了更优的算法——其核心思想是将整数视为“信号“, 通过转换到傅里叶域来更高效地完成乘法运算(傅里叶变换是数学和工程学的核心工具, 应用极其广泛; 若您尚未接触过, 很可能在后续学习中会遇到). 此后多年间, 研究者们不断改进算法, 直到最近哈维(Harvery)和范德霍芬(Van Der Hoeven)才成功实现了时间复杂度为$O(n\log n)$的乘法算法(不过该算法仅在处理真正天文级别的数字时才开始超越舍恩哈格-施特拉森算法). 然而, 尽管取得了这些进展, 我们至今仍未知晓是否存在能在$O(n)$时间内完成两个$n$位数乘法的算法!

0.3 超越算术的算法

对更优算法的探索绝非仅限于加法、乘法或解方程等算术任务. 在过去的数十年间, 图论算法领域涌现出大量突破性成果—包括路径搜索、匹配、生成树、割集和流算法在内的多项发现, 这一领域至今仍是密集研究的重点领域(例如近年来基于电路理论与线性方程求解器之间的意外关联产生了诸多最大流问题上的进展. )这些算法不止被应用于网络流量路由、GPS导航等“天然“应用场景, 更广泛渗透于基因交互图谱结构促进新药研发、投资关联风险计算等多元化领域.

谷歌公司的成立基石是PageRank算法—该算法能够高效地近似计算网络图邻接矩阵(经阻尼处理过后的)的“主特征向量(principle eigenvector)“. Akamai公司的诞生则依托于创新数据结构“一致性哈希”, 该数据结构能够实现哈希桶在多服务器之间的分布式存储. 反向传播算法(backpropagation algorithm)通过将神经网络偏导数计算复杂度从$O(n^2)$降至$O(n),$ 成为深度神经网络近年取得惊人成就的核心支柱. 而基于稀疏约束线性方程求解的压缩感知(compressed sensing)算法, 显著降低了MRI图像分析对数据量和质量的要求, 这一突破对于儿童肿瘤MRI检测具有革命性意义—此前医生需实施麻醉暂停患儿呼吸进行扫描, 此过程常常伴随致命风险.

即便对于毕达哥拉斯时代就开始研究的素数判定这类经典问题, 仍有不断的新发现涌现: 高效的概率算法于1970年代问世, 首个确定性多项式时间算法直至2002年才被发现. 在合数分解这个领域, 1980年代诞生了新算法, 而1990年代的研究成果(本课程后续将继续探讨)更揭示了利用量子力学实现加速算法的诱人前景.

尽管取得诸多进展, 算法领域仍存在悬而未解之谜. 对于大多数自然问题, 我们既无法断定现有算法是否已达到最优, 亦不能确定是否存在更高效的待发现算法. 正如本章开篇引用的Cobham论断所示——即便是数字乘法这个基础问题, 我们至今仍未证明是否存在与加法算法同等高效的乘法算法. 但至少, 我们已掌握了正确的追问方式.

0.4 论负面结果的重要性

寻找更好的算法来解决诸如乘法、解方程、图论问题或将神经网络拟合数据等问题, 无疑是值得付出努力的. 但为何证明这类算法不存在也同样重要? 其中一个动机源于纯粹的好奇心. 研究不可行性结果的另一个原因在于, 它们对应着我们世界的根本限制. 换而言之, 不可行性结果即是自然法则.

以下是一些计算机科学领域之外的不可行性案例(更多案例参见0.7节). 物理学中, 制造永动机的不可能性对应着能量守恒定律; 热机无法突破卡诺定律的限制对应着热力学第二定律; 而超光速信息传输的不可能性则是狭义相对论的基石. 数学领域中, 虽然我们在高中都学过解二次方程的公式, 但将这种公式推广到五次及以上方程的不可能性催生了群论; 无法从前四个公设证明欧几里得第五公设则导致了非欧几何的诞生——这种几何体系最终成为广义相对论的关键基础.

类似地, 计算领域的不可行性结果对应着“计算法则“, 这些法则揭示了任何信息处理装置(无论是基于硅基芯片、神经元还是量子粒子)的根本限制. 更重要的是, 计算机科学家创造了巧妙的方法来利用计算局限性完成特定任务. 例如现代互联网通信大多采用RSA加密方案, 其安全性正是基于(推测性的)大整数高效分解的不可能性; 近年来比特币系统采用“数字金本位“模式——通过“挖矿“解决计算难题来获取新型货币, 而非依赖贵金属支撑.

0.5 本书其余部分的路线图

通常, 当我们试图解决计算问题时—无论是求解线性方程组、寻找矩阵的主特征向量, 还是对网络搜索结果进行排序—采用“一目了然“的标准来描述算法通常已经完全足够. 只要我们找到了解决问题的某种方法, 便会感到满意, 可能并不关心这些解决方法中算法的精确数学模型. 但当我们需要回答诸如“是否存在解决问题$P$的算法? “这类问题时, 就必须在数学上进行更精确的界定.

具体而言, 我们需要: (1)明确定义“解决$P$“的含义, (2)精确定义什么是算法. 有时即使是解决(1)也并非易事, 而(2)则尤其具有挑战性—我们如何(甚至能否)囊括所有潜在的算法设计方法尚未明确. 我们将考察几种简化的计算模型, 并论证尽管这些模型形式简洁, 却足以涵盖所有“合理“的计算实现方式, 包括现代计算设备中采用的所有方法.

一旦我们拥有了这些描述计算的形式化的模型, 我们就能尝试论证计算任务的不可能性, 证明某些问题无法被解决(或者可能无法在我们宇宙的资源限制内解决). 阿基米德有言: 只要给他一个支点和足够长的杠杆, 他就能撬动地球. 我们将看到归约方法如何将一项计算困难度结论转换为众多问题的解决方案, 从而清晰界定可计算和不可计算(或易处理与难处理)问题之间的边界.

在后续章节中, 我们将重新审视计算模型, 探讨随机性或量子纠缠等资源具有的改变这些模型的潜力. 在涉及概率算法的内容中, 我们将窥见随机性如何成为理解计算、信息与通信不可或缺的工具. 同时我们也将认识到, 计算难度可以转化为优势而非障碍, 并且可以用于实现概率算法的“去随机化“. 这些思想同样体现在密码学中—该领域在过去几十年不仅经历的技术革命, 更完成了智力层面的革新, 其诸多成就都构建于本课程探讨的基础之上.

理论计算机科学是一个博大精深的领域, 其分支触及众多科学与工程学科. 本书仅呈现了这个领域非常局部(且带有主观倾向)的样本. 最重要的是, 我希望能将本人对这个领域的热爱至少部分地“传染“给读者——这个深受实践联系启发与丰富的学科, 即便不考虑其应用价值, 其本身也蕴含着深邃而璀璨的美感.

0.5.1 章节之间的依赖关系

本书由以下数个部分组成, 见图0.5.

• 基础知识: 引言、数学背景、和将对象表示为字符串的方法.
• 第一部分: 有限计算(布尔电路) 电路与直线程序的等价性、通用门集合、任意函数的电路实现、电路的字符串表示、通用电路、计数论证法下的电路规模下界
• 第二部分: 均匀计算(图灵机) 图灵机与循环程序的等价性、计算模型等价性(包括RAM机器、$\lambda$演算与元胞自动机)、图灵机构型、通用图灵机存在性、不可计算函数(包括停机问题与Rice定理)、Gödel不完备定理、受限计算模型(正则语言与上下文无关语言)
• 第三部分: 高效计算 时间复杂度定义、时间分层定理、$\mathbf{P}$与$\mathbf{NP}$复杂度类、${\mathbf{P}}_{/poly}$复杂度类、$\text{NP}$完全性与Cook-Levin定理、空间受限计算
• 第四部分: 随机计算 概率基础、随机算法、$\text{BPP}$复杂度类、错误率放大技术、$\text{BPP}\subseteq {\mathbf{P}}_{/poly}$定理、伪随机生成器与去随机化
• 第五部分: 高级专题 密码学、证明与算法(交互式证明与零知识证明、Curry-Howard对应关系)、量子计算

%%{init: {'theme':'dark'}}%%
graph TD;
    p1[**第一部分：有限计算（布尔电路）**
    **有限**输入上的函数
    **定量**研究];
    p2[**第二部分：均匀计算（图灵机）**
    **无限**输入上的函数
    **定性**研究];
    p3[**第三部分：高效计算**
    **任意长度**输入上的函数
    **定量**研究];
    p4[**第四部分随机计算**
    均匀类和非均匀类的关系。将计算难度视为一种资源。];
    p5[**第五部分：高级专题**];
    p1==>p3;
    p1-.->p2;
    p2==>p3;
    p3==>p4;
    p4==>p5;

本书主要采用线性叙事结构, 各章节内容环环相扣, 但以下例外情况请注意: $\lambda$演算(第8.5节)、Gödel不完备定理(第11章)、自动机/正则表达式与上下文无关文法(第10章)以及空间受限计算(第17章)的内容在后续章节中不再使用, 教师可自主选择是否讲授这些章节.

第二部分(均匀计算/图灵机)不强烈依赖第一部分(有限计算/布尔电路)的内容, 稍作调整后可互换教学顺序. 布尔电路在第三部分(高效计算)用于证明$\text{P}\subseteq {\mathbf{P}}_{/poly}$和Cook-Levin定理, 在第四部分(用于证明$\text{BPP}\subseteq {\mathbf{P}}_{/poly}$和去随机化)以及第五部分(密码学和量子计算专题)中均有应用.

第五部分(高级专题)各章节内容相互独立, 可按任意顺序讲授.

基于本教材的课程建议完整覆盖第一、二、三部分(可选择跳过$\lambda$演算、第11章、第10章或第17章), 随后完整或部分讲授第四部分(随机计算), 最后根据师生兴趣精选第五部分的高级专题进行补充教学.

0.6 习题

0.7 参考书目

若要简要了解本书的主要内容, 伯纳德·查泽(Bernard Chazelle)论述《算法作为现代科学范式》的精彩文章是不可多得的优质资料. 摩尔与默滕斯的著作(Moore, Mertens, 2011)对计算理论进行了卓越而全面的概述, 涵盖本章及本书后续讨论的诸多内容. 阿伦森的专著(Aaronson, 2013)同样值得推荐, 其中探讨了许多相关主题.

关于巴比伦人使用的算法, 可参阅高德纳的论文和诺伊格鲍尔的经典著作. 本章提及的多数算法可见于以下教材: 科曼、莱瑟森、里维斯特和斯坦(Cormen, Leiserson, Rivest, Stein, 2009), 克莱伯格与塔多斯(Kleinberg, Tardos, 2006), 达斯古普塔、帕帕季米特里乌和瓦齐拉尼(Dasgupta, Papadimitriou, Vazirani, 2008), 以及杰夫·埃里克森的教材. 埃里克森的著作可免费在线获取, 其中对递归算法(特别是卡拉楚巴算法)进行了精彩论述.

卡拉楚巴在本人著作(Karatsuba, 1995)中讲述了发现乘法算法的经过. 如前所述, 图姆和库克(Toom, 1963)(Cook, 1966)、舍恩哈格与施特拉森(Schönhage, Strassen, 1971)、富雷尔(Fürer, 2007)以及近期的哈维与范德霍芬(Harvey, Van Der Hoeven, 2019)相继做出了改进, 相关综述可参阅这篇文章. 后两篇论文的关键基础是快速傅里叶变换算法. 约翰·图基在冷战背景下(重新)发现该算法的精彩故事记载于(Cooley, 1987)(之所以称为“重新发现“, 是因为后世研究表明该算法可追溯至高斯时代(Heideman, Johnson, Burrus, 1985)). 快速傅里叶变换在下文提及的部分著作及杰夫·埃里克森的在线课程中均有涉及, 另可参考大卫·奥斯汀的科普文章. 快速矩阵乘法由施特拉森(Strassen, 1969)首创, 此后该领域持续涌现研究成果, 推荐阅读布拉泽的自含式综述(Bläser, 2013).

神经网络快速求导的反向传播算法由韦伯斯发明(Werbos, 1974). 网页排名算法由拉里·佩奇和谢尔盖·布林提出(Page, Brin, Motwani, Winograd, 1999), 与克莱伯格的HITS算法(Kleinberg, 1999)密切相关. 阿卡迈公司的创立基于一致性哈希数据结构(Karger, Lehman, Leighton, Panigrahy, Levine, Lewin, 1997). 压缩感知技术历史悠久, 其中两篇奠基性论文为(Candes, Romberg, Tao, 2006)和(Donoho, 2006). (Lustig, Donoho, Santos, Pauly, 2008)综述了压缩感知在MRI中的应用, 另可参阅埃伦伯格的科普文章(Ellenberg, 2010). 确定性多项式时间素性检测算法由阿格拉瓦尔、卡亚尔和萨克斯纳给出(Agrawal, Kayal, Saxena, 2004).

我们简要提及了数学中的经典不可行性结果, 包括欧几里得第五公设的不可证明性、尺规作图三等分角的不可能性, 以及五次方程无法通过根式求解的特性. 陶哲轩的博客文章给出了角三等分不可能性的几何证明(这是古希腊时期留下的三大几何难题之一). 马里奥·利维奥的著作(Livio, 2005)阐述了这些不可行性结论背后的背景与思想. 当前前沿研究正尝试运用计算复杂性解释物理学基本问题, 例如理解黑洞特性以及调和广义相对论与量子力学的矛盾.

1: 原文此处的内容为“Exercise 0.4“, 疑为作者笔误

2: 正如我们将在第21章(Chapter 21)中看到的, 几乎所有依赖密码学的企业都需要以某些算法的不存在性为前提. 特别地, RSA安全公司(RSA Security)的成立正是基于RSA加密系统的安全性, 该系统的前提正是假定不存在能高效计算大整数质因数分解的算法.

3: 提示: 使用归纳法进行证明——假设该结论对所有从$1$到$m$的$n$值成立, 并证明其对$m+1$同样成立.

4: 首先证明当$n=k^t$(其中$t$为自然数)时的特殊情况, 此时可通过将矩阵分割成$k\times k$块的方式进行递归处理.

• 数学背景
  • 学习目标
  • 1.1 本章: 读者的参考手册
  • 1.2 前置数学知识的概览
  • 1.3 阅读数学文本
    • 1.3.1 定义
    • 1.3.2 断言: 定理、引理、主张
    • 1.3.1 证明
  • 1.4 基础离散数学对象
    • 1.4.1 集合
    • 1.4.2 特殊集合
    • 1.4.3 函数
    • 1.4.4 图
    • 1.4.5 逻辑运算符与量词
    • 1.4.6 求和与求积的量词
    • 1.4.7 解析公式: 约束变量与自由变量
    • 1.4.8 渐近分析与大$O$表示法
    • 1.4.9 关于大$O$表示法的一些“经验法则“
  • 1.5 证明
    • 1.5.1 证明与程序
    • 1.5.2 证明的书写风格
    • 1.5.3 证明的方法
  • 1.6 扩展示例: 拓扑排序
    • 1.6.1 数学归纳法
    • 1.6.2 通过归纳证明结论
    • 1.6.3 最小性和唯一性
  • 1.7 本书所用到的符号及规范
    • 1.7.1 变量命名规范
    • 1.7.2 一些惯用表达
  • 1.8 习题
  • 1.9 参考书目

数学背景

学习目标

• 学习基本的数学概念, 如几何、函数、数字、逻辑运算符及量词、字符串和图.
• 严格地定义大$O$表示法.
• 归纳证明法.
• 练习如何阅读数学 定义、陈述与证明.
• 将直观的论证转化为严谨的证明.

在本章中, 我们将会介绍一些将在本书中用到的数学概念. 这些概念一般会在“计算机科学中的数学“或“离散数学“等课程或课本中讲解. 有关这些主题的几份可在线免费获取优秀资源, 请参阅“参考书目“部分(第1.9节).

一个数学家的辩白. 部分学生可能会好奇为什么这本书包含如此多的数学, 这是因为数学就是一门能够简洁而精确描述概念的语言. 在这本书中, 我们使用数学来描述计算的概念. 比如说, 我们将思考诸如“是否存在一种高效算法来求取给定整数的质因数?“这样的问题(我们将看到这个问题尤为有趣, 它甚至触及了从互联网安全到量子力学等跨度极大的问题! )若要精准的描述这些问题, 我们需要对算法这一概念以及算法的高效性给出精准的定义. 此外, 由于无法通过实验证明某种算法不存在, 唯一能证实算法不存在性的方式就是数学证明.

1.1 本章: 读者的参考手册

基于你已有的数学背景, 你有两种阅读本章的方式:

• 如果你已经学习过“离散数学“、“计算机科学中的数学“或任何类似课程, 则无需阅读整章内容, 只需要快速地阅读第1.2节来了解我们会用到什么数学工具与第1.7节来了解本书所用符号, 便可跳转至后续章节. 或者, 你也可以放松心情通读本章, 既熟悉本书所用的符号体系, 顺便品味(或忍受)笔者融于字里行间的哲学思考与幽默尝试.
• 若相关基础较为薄弱, 可以参考第1.9节中提供的学习资源. 本章虽然已经涵盖了所有所需知识点, 但系统性地学习相关知识点可能对你更有帮助. 数学学习重在实践, 通过独立完成练习才能真正掌握这些内容.
• 建议你同时开始回顾离散概率论的相关知识, 本书后续章节(见第18章)将涉及这部分内容.

1.2 前置数学知识的概览

我们将使用的主要数学概念如下所示. 此处仅列出这些概念, 其具体定义将在本章后续部分给出. 若您已熟悉所有这些内容, 可以直接跳至第1.7节查看我们使用的完整符号列表.

• 证明: 最重要的是, 本书包含大量形式化数学推理, 涵盖数学定义、陈述与证明.
• 集合及集合运算: 我们将广泛使用数学集合. 涉及到的集合关系包括属于($\in )$与包含($\subseteq ),$ 以及集合运算, 主要是并集($\cup )$、交集($\cap )$与差集($\setminus ).$
• 笛卡尔积(Cartesian product)与克林星号(Kleene star)运算: 两个集合$A$与$B$的笛卡尔积, 记作$A\times B$(即由所有满足$a\in A$且$b\in B$的所有有序对$(a,b)$构成的集合), $A^n$表示$n$阶笛卡尔积(例如$A^3=A\times A\times A),$ 而$A^{\ast }$(称为 克林星号 )表示所有$n\in \{0,1,2,\dots \}$对应的$A^n$的并集.
• 函数: 函数的定义域和陪域, 以及函数的性质(如单射函数和满射函数), 还有部分函数(即不同于全函数的, 对于定义域内部分元素可能存在未定义情况的函数).
• 逻辑运算: 常用操作包括逻辑与($\wedge )$、逻辑或($\vee )$、逻辑非($\neg )$等, 以及存在量词($\exists )$和全称量词($\forall ).$
• 基础组合数学: 诸如$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$(表示大小为$n$的集合中所有$k$元子集的数量)等概念.
• 图论: 无向图和有向图、连通性、路径和环.
• 大$O$表示法: 使用$O,o,\Omega ,\omega ,\theta$符号分析函数的渐进增长性.
• 离散概率: 我们将使用概率论, 特别是基于有限概率空间(如抛掷$n$枚硬币)的概率论, 包括随机变量、期望和浓度等概念. 概率论仅在本书后半部分使用, 我们将在第18章先行复习. 然而概率推理是一项精妙(且极其实用)的技能, 尽早开始掌握总是有益的.

本章后续部分将简要回顾上述概念. 既是为了帮助读者重温可能已经生疏的知识, 也是为了介绍我们的符号与约定——这些约定有时可能与你之前接触过的版本有所不同.

1.3 阅读数学文本

数学家使用各种专业术语的原因, 与工程、法律、医学等其他众多领域并无差别: 我们需要精确的术语, 并为频繁使用的概念引入简洁表达. 数学文本往往在单个句子中蕴含极高的信息密度, 因此关键在于缓慢而仔细地阅读, 逐个符号解析.

随着练习时间逐渐增长, 你将发现阅读数学文本变得越来越轻松, 且专业术语也不再是问题. 更重要的是, 数学文本阅读能力是从本书中能够获得的极具迁移价值的技能之一. 我们的世界正飞速变化——这不仅体现在技术领域, 更延伸至医学、经济学、法律乃至文化等人类实践的方方面面. 无论你未来方向如何, 都很可能会接触到包含前所未见新概念的文本(参见图 1.1与图 1.2中两个当代“热点领域“的例子). 掌握内化并应用新定义的能力至关重要. 在数学课程相对安全稳定的学习环境中, 这种技能更容易被掌握——至少你可以确信所有概念都有完整定义, 并能随时向教学人员答疑解惑.

数学文本的基本构成要素有三: 定义 、断言 与 证明.

1.3.1 定义

数学家经常在已有的概念上定义新的概念. 比如, 以下是一个你可能曾经见过的数学定义(并且我们很快还会再见到):

定义 1.1阐述了一个简单的概念, 但即便如此它也使用了大量符号. 阅读此类定义时, 一边阅读一边用笔进行标注往往很有帮助(见图 1.3). 例如当看到诸如$f$、$S$或$x$等符号时, 务必确认其指代的对象的类别: 是集合、函数、元素、数字, 还是小妖怪? 你可能还会发现, 向朋友(或对自己)用语言解释这一定义会很有帮助.

1.3.2 断言: 定理、引理、主张

定理、引理、断言等都是对已定义概念的真命题. 将特定命题称为“定理“、“引理“还是“断言“属于主观判断, 并不改变其数学实质——三者均指代已被证明为真的命题. 区别在于: 定理指代值得铭记和强调的重要结论; 引理通常指技术性结论, 其自身未必重要但能有效辅助其他定理的证明; 断言则是为证明更重大结论而使用的“过渡性“命题, 其自身价值并不受关注.

1.3.1 证明

数学证明是用以证实定理、引理及断言真实性的论证过程. 我们将在下文1.5节讨论证明, 其核心在于数学证明的标准极为严苛. 与其他领域不同, 数学证明必须是“无懈可击“的论证, 确保证明对象无可置疑为真. 本节涉及的数学证明示例参见练习 1.1及1.6节. 如前言所述, 总体而言: 理解定义比掌握定理更重要, 理解定理陈述比掌握其证明过程更重要.

1.4 基础离散数学对象

在本节中, 我们将快速回顾本书中所用的一些数学对象(你当然也可以把这些叫做数学中的“基本数据结构“).

1.4.1 集合

一个集合是一些对象的无序容器. 例如, $S=\{2,4,7\}$表示$S$指代一个包含数字$2$、$4$、$7$的集合(我们使用$2\in S$来表示$2$是$S$中的一个元素. )注意集合$\{2,4,7\}$与$\{7,4,2\}$是相同的, 因为它们拥有相同的元素. 同时, 一个集合要么包含一个元素, 要么不包含一个元素, 不存在“包含两次“的概念, 因此我们甚至可以将同一个集合$S$写作$\{2,2,4,7\}$(尽管这样写有些奇怪). 有限集合的 基数 (cardinality), 即一个集合包含的元素的数量, 记作$|S|$(基数亦可以定义在 无限 集上, 见第1.9节的参考资料). 因此在上例中$|S|=3.$ 若集合$S$的元素都是集合$T$的元素, 则称$S$为$T$的一个子集, 记作$S\subseteq T$(我们亦可以称$T$为$S$的一个超集. )比如, $\{2,7\}\subseteq \{2,4,7\}.$ 不包含任何元素的集合称作空集, 写作$\varnothing .$ 如果$A$是$B$的一个子集且$A$不等于$B,$ 则我们称$A$为$B$的一个真子集, 记作$A⊊B.$

我们可以通过将其元素全部列出来定义集合, 也可以通过写下集合元素满足的一个条件来定义集合, 例如: $$偶数集=\{x|对于某个非负整数y,有x=2y\}$$ 当然, 同一集合有多种表示方式, 我们常会使用直观的记号列出几个示例来说明规则. 例如也可将$偶数集$定义为: $$偶数集=\{0,2,4,\dots \}$$ 注意集合可以是有限的(如$\{2,4,7\})$或无限的(如$\text{偶数集}).$ 集合的元素不必是数字, 例如英语元音的集合$\{a,e,i,o,u\},$ 或按2010年人口普查的美国百万人口城市集合$\{\text{New York, Los Angeles, Chicago, Houston, Philadelphia, Phoenix, San Antonio, San Diego, Dallas}\}.$ 集合甚至可以包含其他集合作为元素, 例如$\{1,2,3\}$所有偶数大小子集构成的集合$\{\varnothing ,\{1,2\},\{2,3\},\{1,3\}\}.$

集合运算: 集合$S$与的$T$的并集记作$S\cup T,$ 包含所有属于$S$或属于$T$的元素. 交集记作$S\cap T,$ 包含同时属于$S$和$T$的元素. 差集记作$S\setminus T$(部分文献中记作$S-T),$ 包含属于$S$但不属于$T$的元素.

元组、列表、字符串、序列: 元组是有序的对象容器, 例如$(1,5,2,1)$是包含四个元素的元组(称为$4$-元组或四元组). 由于元组是有序的, 该元组不同于四元组$(1,1,5,2)$或三元组$(1,5,2).$ $2$-元组亦称为有序对. 术语“元组“与”列表“可互换使用. 若某个元组中的元素均来自于某个有限集$\Sigma$(如$\{0,1\}),$ 则称为字符串. 类比集合, 我们将元组$T$的长度记作$|T|.$ 与集合类似, 元组亦有无限形式. 例如由所有完全平方数组成的元组$(1,4,9,\dots ).$ 无限的有序容器称为序列, 有时亦称作“无限序列“以强调这一点. “有限序列“是元组的同义词. (可将集合$S$中元素的序列$(a_0,a_1,a_2,\dots )$视为函数$A:\mathbb{N}\to S$(其中对任意$n\in \mathbb{N}$满足$a_n=A(n)).$ 类似地, 可将$S$中元素的$k$-元组视为函数$A:[k]\to S.$ )

笛卡尔积: 若$S$与$T$是集合, 则其笛卡尔积记作$S\times T,$ 是由所有满足$s\in S$且$t\in T$的有序对$(s,t)$构成的集合. 例如, 若$S=\{1,2,3\}$且$T=\{10,12\},$ 则$S\times T$包含六个元素: $(1,10),(2,10),(3,10),(1,12),(2,12),(3,12).$ 相似的, 若$S,T,U$为集合, 则$S\times T\times U$为由所有满足$s\in S$、$t\in T$、$u\in U$的三元组$(s,t,u)$构成的集合. 更加一般地, 对任意正整数$n$及集合$S_0,\dots ,S_{n-1},$ 用$S_0\times S_1\times \cdots \times S_{n-1}$表示满足对每个$i\in \{0,\dots ,n-1\}$有$s_i\in S_i$的有序$n$-元组$(s_0,\dots ,s_{n-1})$的集合. 对任意集合$S,$ 将$S\times S$记作$S^2,$ $S\times S\times S$记作$S^3,$ $S\times S\times S\times S$记作$S^4,$ 依此类推.

1.4.2 特殊集合

在本书中会反复用到数个特殊集合. 集合 $$\mathbb{N}=\{0,1,2,\dots \}$$

包含了所有的自然数, 即非负整数. 对于任意的自然数$n\in \mathbb{N},$ 定义集合$[n]$为$\{0,\dots ,n-1\}=\{k\in \mathbb{N}:k<n\}$($\mathbb{N}$与$n$均从$0$开始计数, 与此同时诸多文献中这两个集合是从$1$开始的计数的. 从零开始计数只是一个约定俗成的做法, 只要保持一致性, 并不会产生太大差异. )

我们偶尔也会使用集合$\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$来表示所有(负的和非负的)整数, 同时使用$\mathbb{R}$来表示所有实数(这个集合不仅包含整数, 同时也包含分数与无理数, 例如, $\mathbb{R}$包含诸如$+0.5$、$-\pi$等的数字. )我们使用${\mathbb{R}}_{+}$来表示所有正实数的集合$\{x\in \mathbb{R}:x>0\}.$ 这个集合有时亦写作$(0,\infty ).$

字符串: 另外一个我们经常会用到的集合是 $$\{0,1{\}}^n=\{(x_0,\dots ,x_{n-1}):x_0,\dots ,x_{n-1}\in \{0,1\}\}$$ 这个集合包含了所有长度为$n$($n$为任意自然数)的二进制字符串. 换句话说, $\{0,1{\}}^n$是包含所有由$0,1$组成的$n$-元组的集合. 这与我们前文中的符号一致: $\{0,1{\}}^2$是笛卡尔积$\{0,1\}\times \{0,1\},$ $\{(0,1){\}}^3$是笛卡尔积$\{(0,1)\}\times \{(0,1)\}\times \{(0,1)\},$ 依此类推.

我们将字符串$(x_0,x_1,\dots ,x_{n-1})$简单地写作$x_0{x}_1\cdots x_{n-1}.$ 例如, $$\{0,1{\}}^3=\{000,001,010,011,100,101,110,111\}$$ 对于所有字符串$x\in \{0,1{\}}^n$与$i\in [n],$ 我们将$x$的第$i$个元素记作$x_i.$

我们也经常会使用包含所有长度二进制字符串的集合, 即 $$\{0,1{\}}^{\ast }=\{(x_0,\dots ,x_{n-1}):n\in \mathbb{N},,x_0,\dots ,x_{n-1}\in \{0,1\}\}$$ 另一个表示这个集合的方式是 $$\{0,1{\}}^{\ast }=\{0,1{\}}^0\cup \{0,1{\}}^1\cup \{0,1{\}}^2\cup \cdots$$ 或者更为简洁的 $$\{0,1{\}}^{\ast }=\bigcup _{n\in \mathbb{N}}\{0,1{\}}^n$$ 集合$\{0,1{\}}^{\ast }$包含了“长度为$0$的字符串“或“空字符串“, 我们将这个字符串记作$\text{""}$(此处我们使用与大部分编程语言一致的符号, 其他文献可能会使用$ϵ$或$\lambda$来表示空字符串).

推广星号操作: 对于任意集合$\Sigma ,$ 我们定义 $${\Sigma }^{\ast }=\bigcup _{n\in \mathbb{N}}{\Sigma }^n$$ 例如, 若$\Sigma =\{a,b,c,d,\dots ,z\},$ 则${\Sigma }^{\ast }$表示字母表a-z上所有有限长度字符串的集合.

连接操作: 两个字符串$x\in {\Sigma }^n$与$y\in {\Sigma }^m$的连接是指将$y$书写在$x$后形成的$(n+m)$长度的字符串$xy.$ 具体而言, 若$x\in \{0,1{\}}^n$且$y\in \{0,1{\}}^m,$ 则$xy$等于满足以下条件的字符串$z\in \{0,1{\}}^{n+m}:$ 当$i\in [n]$时$z_i=x_i,$ 当$i\in \{n,\dots ,n+m-1\}$时$z_i=y_{i-n}.$

1.4.3 函数

若$S$与$T$为非空集合, 则从$S$到$T$的函数(记作$F:S\to T)$会将每个元素$x\in S$关联到一个元素$F(x)\in T.$ 集合$S$称为函数$F$的定义域, 集合$T$称为$F$的陪域. 函数$F$的像是指集合$\{F(x)|x\in S\},$ 即由所有被映射的输入元素对应的输出元素组成的$F$的陪域子集(有些文献使用“值域“一词表示函数的像, 而另一些文献使用”值域“表示函数的陪域. 因此我们将完全避免使用“值域“这一术语. )与集合类似, 我们可以通过列出函数对$S$中所有元素给出的取值表或通过规则来定义函数. 例如, 若$S=\{0,1,2,3,4,5,6,7,8,9\}$且$T=\{0,1\},$ 则下表定义了一个函数$F:S\to T.$ 注意该函数与规则$F(x)=(x\mathrm{mod}2)$定义的函数相同.

若$F:S\to T$满足对所有$x\ne y$均有$F(x)\ne F(y),$ 则称$F$是单射(见定义 1.1, 亦称为单射函数). 若$F$满足对每个$y\in T$均存在某个$x\in S$使得$F(x)=y,$ 则称$F$是满射(亦称作满射函数). 既是单射又是满射的函数称为双射函数或双射. 从集合$S$到自身的双射亦称为$S$的排列. 若$F:S\to T$是双射, 则对于每个$y\in T$均存在唯一的$x\in S$使得$F(x)=y.$ 我们将该值$x$记作$F^{-1}(y).$ 注意$F^{-1}(y)$本身也是从$T$到$S$的双射(你能明白为什么吗? ).

给出两个集合之间的双射通常是证明集合大小相同的有效方法. 事实上, “$S$与$T$具有相同基数“的标准数学定义就是存在一个双射$f:S\to T.$ 此外, 若存在从$S$到集合$\{0,\dots ,n-1\}$的双射, 则定义集合$S$的基数为$n.$ 正如我们将在本书后面看到的, 这个定义可以推广到无限集合的基数定义.

部分函数(又译偏函数): 我们有时会关注从$S$到$T$的部分函数. 部分函数允许在$S$的某个子集上未定义. 也就是说, 若$F$是从$S$到$T$的偏函数, 则对每个$s\in S,$ 要么(如标准函数的情况)存在$T$中的元素$F(s),$ 要么$F(s)$未定义. 例如, 部分函数$F(x)=\sqrt{x}$仅定义在非负实数上. 当需要偏函数和标准(即非部分)函数时, 我们称后者为全函数. 当我们不加限定地说“函数“时, 指的是全函数.

部分函数的概念是函数的严格推广, 因此每个函数都是部分函数, 但并非每个部分函数都是函数(也就是说, 对于任意非空集合$S$与$T,$ 从$S$到$T$的偏函数集合是从$S$到$T$的全函数集合的真超集. )当需要强调从$A$到$B$的函数$f$可能不是全函数时, 我们写作$f:A{\to }_{p}B.$ 我们也可以将从$S$到$T$的偏函数视为从$S$到$T\cup \{\perp \}$的全函数, 其中$\perp$是一个特殊的“失败符号“. 因此, 我们可以说$F(x)=\perp ,$ 而不是$F$在$x$处未定义.

关于函数的基本事实: 验证能否证明以下结论是复习函数知识的绝佳方式:

• 若$F:S\to T$和$G:T\to U$是单射函数, 则它们的复合函数$H:S\to U$(定义为$H(s)=G(F(s)))$也是单射.
• 若$F:S\to T$是单射, 则存在一个满射函数$G:T\to S,$ 使得对于每个$s\in S$均有$G(F(s))=s.$
• 若$G:T\to S$是满射, 则存在一个单射函数$F:S\to T,$ 使得对于每个$s\in S$均有$G(F(s))=s.$
• 若$S$与$T$是非空有限集合, 则以下条件相互等价: (a) $|S|\le |T|;$ (b) 存在单射函数$F:S\to T;$ (c) 存在满射函数$G:T\to S.$ 这些等价关系实际上对无限集合$S$和$T$亦成立. 对于无限集合, 条件(b)(或等价的条件(c))是$|S|\le |T|$的公认定义.

让我们以其中一个事实为例进行证明:

1.4.4 图

图在计算机科学及众多其他领域中无处不在. 图可以用于建模非常多的数据类型, 包括但不限于社交网络、调度约束、道路网络、深度神经网络、基因相互作用、观测值之间的相关性. 几种图的正式定义将在下面给出, 但如果你没有在先前的课程中了解过图, 我强烈建议你从第1.9节中的资料中详细了解它们.

图有两种基本类型: 无向图与有向图.

基于这个定义, 我们可以定义关于图与顶点的几个性质. 我们将$u$的相邻节点的个数成为$u$的度数. 图中的一条路径是一个元组$(u_0,\dots ,u_k)\in V^{k+1}$(其中$k>0),$ 且满足对每个$i\in [k],$ $u_{i+1}$都是$u_i$的相邻节点. 简单路径是指所有$u_i$均不重复的路径$(u_0,\dots ,u_{k-1}).$ 环是指满足$u_0=u_k$的路径$(u_0,\dots ,u_k).$ 若两个顶点$u,v\in V$满足$u=v$或存在一条从$u_0=u$到$u_k=v$的路径, 则称这两个顶点是联通的. 当图中每对顶点都联通时, 我们称该图是连通图.

下面是一些关于无向图的基本事实. 我们将为它们给出一些非正式的论证, 但完整证明作为练习留待读者自行完成(完整证明可以在第1.9节中的诸多资源中找到).

通过观察可知: 每条边$\{u,v\}$会对度数总和贡献两次(一次作用于$u,$ 另一次作用于$v),$ 由此可证明引理 1.2.

通过将路径$(u,u_1,u_2,\dots ,u_{k-1},v)$与路径$(v,u_1^{\prime },\dots ,u_{k-1}^{\prime },w)$拼接, 得到连接$u$与$w$的路径$(u,u_1,\dots ,u_{k-1},v,u_1^{\prime },\dots ,u_{k^{\prime }-1}^{\prime },w),$ 即可证明引理 1.3.

通过“捷径修剪法“可证明引理 1.4: 若某路径中同一节点$w$出现两次, 则移除其间的循环段(见图 1.5). 将这一直观论证转化为形式化证明是很好的练习:

度数和连通性的概念亦可自然推广至有向图, 其定义如下:

有向图可能同时包含边$u\to v$和$v\to u,$ 此时$u$和$v$互为入邻居和出邻居. 顶点$u$的入度是其入邻居的数量, 出度是其出邻居的数量. 图中的路径是指元组$(u_0,\dots ,u_k)\in V^{k+1}$(其中$k>0),$ 且对每个$i\in [k]$有$u_{i+1}$是$u_i$的出邻居. 与无向图情形类似, 简单路径是指所有$u_i$均不相同的路径$(u_0,\dots ,u_{k-1}),$ 环是指满足$u_0=u_k$的路径$(u_0,\dots ,u_k).$ 我们经常关注的一类有向图是有向无环图(Directed Acyclic Graph, DAG), 顾名思义即为不含环的有向图:

上述引理在有向图中均有对应版本. 其证明(与无向图情形基本一致)将作为习题留给读者.

1.4.5 逻辑运算符与量词

如果$P$和$Q$是可真可假的陈述, 则$P$与$Q$(记为$P\wedge Q)$是一个当且仅当$P$和$Q$同时为真时才成立的陈述; 而$P$或$Q$(记为$P\vee Q)$是一个当且仅当$P$或$Q$为真是成立的陈述. $P$的否定记作$\neg P$或$\overline{P},$ 当且仅当$P$为假时该陈述为真.

假设$P(x)$是一个依赖于某个参数$x$(有时亦称为自由变量)的陈述, 其特性在于: 对于从集合$S$中取值的每一个$x$的具体赋值, $P(x)$都会有明确的真值. 例如$x>7$这个陈述本身没有固有真值, 但当我们用具体实数代入$x$时, 它就会成为真或假的命题. 我们用${\forall }_{x\in S}P(x)$表示这样一个陈述: 当且仅当对所有$s\in S$都有$P(x)$为真时, 该陈述为真. 用${\exists }_{x\in S}P(x)$表示这样一个陈述: 当且仅当存在某个$x\in S$使得$P(x)$为真时, 该陈述为真.