• 高效计算 : 非正式导论
  • 学习目标
  • 12.1 图上问题
    • 12.1.1 找到图中的最短路
    • 12.1.2 找到图中的最长路
    • 12.1.3 找到图中的最小割
    • 12.1.4 最大流最小割和线性规划
    • 12.1.5 找到图中的最大割
    • 12.1.6 关于凸性的说明
  • 12.2 图之外的问题
    • 12.2.1 SAT
    • 12.2.2 解线性方程组
    • 12.2.3 解二次方程组
  • 12.3 更进阶的例子
    • 12.3.1 矩阵的行列式
    • 12.3.2 矩阵的积和式
    • 12.3.3 寻找零和博弈平衡
    • 12.3.4 寻找纳什均衡
    • 12.3.5 素性测试
    • 12.3.6 整数分解
  • 12.4 我们的已学内容
  • 12.5 习题
  • 12.6 文献注释
  • 12.7 进一步探索

高效计算 : 非正式导论

学习目标

• 在更高层次描述一些有趣的计算问题.
• 多项式时间和指数时间的差异.
• 例子关于能够得到高效算法的科技
• 例子关于那些看上去很小的问题中的不同能够造成时间复杂度的巨大差异.

目前为止, 我们已经讨论了哪些函数是 可计算 的, 哪些是 不可计算 的. 在本章中, 我们将以一个更好的视角来审视: 如何计算一个函数的时间, 即这个时间 关于输入长度的函数 是什么. 时间复杂度对理论和实践都极其重要, 不过在导论课, 编码面试, 和软件开发中, 类似于 “$O(n)$ 运行时间” 的术语常常被以非正式的方式使用. 人们通常对什么是线性时间算法没有准确定义, 而是认为 “看到时自然就懂了”. 在本书中, 我们会使用先前章节中建立的数学计算模型精确地定义运行时间. 这使我们能够提出 (或有时回答) 这样的问题:

• “是否存在一个能在 $O(n^2)$ 时间内计算但不能在 $O(n)$ 时间内计算的函数?”

• “是否存在自然的问题, 满足最优的算法 (不仅是已知最优) 需要 $2^{\Omega (n)}$ 时间?”

虽然 $O(n)$ 和 $O(n^2)$ 之间的差距在实践中可能很大, 但在本书中, 我们将关注多项式运行时间和指数运行时间的更大差距. 我们将会看到, 多项式时间和指数时间之间的差距通常是对计算模型的选择不敏感的, 无论你选择图灵机, RAM 机 还是并行集群, 一个多项式算法一定还是多项式算法, 同理, 一个指数算法仍会是指数算法. 计算中的一个有趣现象是: 运行时间往往存在一种 “阈值现象” 或 “零一律”. 许多自然问题的运行时间存在“两极分化“的现象, 要么可以在阶数不大的多项式运行时间 (如 $O(n^2)$ 或 $O(n^3))$ 内解决, 要么就需要指数时间 (如至少 $2^{\Omega (n)}$ 或 $2^{\Omega (\sqrt{n})})$ 才能解决. 这种现象的原因还未完全被明晰, 但通过 第 15 章 中对NP 完全性的介绍, 我们可以对其一窥究竟.

本章仅仅是对计算问题和高效算法宏大图景的一瞥. 如果你想要更深入地探索算法和数据结构 (我很希望你能这样做!), 参考文献中有一些非常棒地文章可以供你阅读, 其中一些可以在网络上免费获得.

12.1 图上问题

本章中我们将会讨论一些重要的计算问题. 其中大部分都会包含 图. 在之前的章节中我们已经遇到过了图 (另见 第 1.4.4 节), 不过我们将会快速的回顾一下基础的记号. 一个图 $G$ 包含 点集 $V$ 和 边集 $E,$ 其中每条边都是一个点的二元组. 我们通常把 $n$ 记为点集大小 (且事实上通常认为点集 $V$ 为 $[n],$ 即 $0$ 到 $n-1$ 间的整数). 在有向图中, 一条边是一个有序的二元组 $(u,v),$ 有时也记为 $\overrightarrow{uv}.$ 在无向图中, 一条边是一个无序的二元组 (或为集合) $\{u,v\},$ 有时也记为 $\overline{uv}$ 或 $u\sim v.$ 一个等价的视角为, 一张无向图对应着一个满足若存在边 $\overrightarrow{uv}$ 则一定存在边 $\overrightarrow{vu}$ 的有向图. 在本章中我们只考虑无向简单图 (简单图为没有重边和自环的图). 图可以由邻接表或者邻接矩阵表达. 我们可以 $O(n^2)$ 次操作转化这两种表达方式, 因此我们在大部分情况下认为他们是等价的.

图在计算机科学和其他科学中都十分常见, 因为图可以作为许多常见数据的完美模型. 这里的数据不止是那些 “显然的” 数据如: 路网 (将地点视为点, 路段视为边), 互联网 (将网页视为节点, 链接视为边), 社交网络 (将人视为点, 朋友关系视为边). 图还能表示数据间的相关性 (如特征观测图, 其中边代表倾向于共同出现的特征), 因果关系 (如, 基因调节网络, 其中基因与其衍生的基因产物相连), 或是系统的状态空间 (例如, 物理系统的配置图, 其中边代表彼此之间可以一步到达的状态).

12.1.1 找到图中的最短路

最短路问题 的任务是, 给定一个图 $G=(V,E)$ 和两个顶点 $s,t\in V,$ 找到 $s$ 和 $t$ 之间最短路径的长度 (如果该路径存在). 也就是说, 我们想要找到最小的数字 $k,$ 使得存在顶点 $v_0,v_1,\dots ,v_k$ 满足 $v_0=s,$ $v_k=t,$ 并且对于每个 $i\in \{0,\dots ,k-1\},$ $v_i$ 和 $v_{i+1}$ 之间都有一条边 . 形式化地, 我们定义 $MINPATH:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ 为这样一个函数: 在输入三元组 $(G,s,t)$ (以字符串形式表示) 时, 输出数字 $k,$ 为 $G$ 中 $s$ 和 $t$ 之间最短路径的长度; 如果不存在这样的路径, 则输出字符串 no path. (在实践中, 人们通常不仅想找到路径长度, 还想找到实际的路径; 事实证明, 计算路径长度的算法通常会产生实际路径作为副产品, 因此我们关于计算长度任务所说的一切, 同样适用于寻找路径的任务).

如果每个顶点至少有两个邻居, 那么从 $s$ 到 $t$ 的路径数量可能会达到 指数级, 但幸运的是, 我们不必枚举所有路径就能找到最短路径. 我们可以使用 广度优先搜索 (BFS) 来寻找最短路径, 即按顺序枚举 $s$ 的邻居, 然后是邻居的邻居, 依此类推. 如果我们用列表维护邻居, 可以在 $O(n^2)$ 时间内执行 BFS; 而使用 队列, 我们可以在 $O(m)$ 时间内完成, 其中 $m$ 是边的数量. ¹ Dijkstra 算法 是 BFS 在 带权 图上广为人知的推广。 计算函数 $MINPATH$ 的算法将在 算法 12.1 被更形式化描述.

由于我们仅将满足 $D[w]=\infty$ 的顶点 $w$ 加入队列 (并随后立即将 $D[w]$ 设置为具体的数值), 我们永远不会将同一个顶点入队超过一次, 因此算法最多执行 $n$ 次 “push” 和 “pop” 操作. 对于每个顶点 $v,$ 内部循环运行的次数等于 $v$ 的度数, 因此总运行时间与所有顶点度数的总和成正比, 而该总和等于边数 $m$ 的两倍. 算法 12.1 返回正确答案是因为顶点是按照它们到 $s$ 的距离顺序被加入队列的, 因此在访问完所有比 $t$ 更接近 $s$ 的顶点后, 我们才会到达 $t.$

12.1.2 找到图中的最长路

最长路径问题 是指在给定的图 $G$ 中, 寻找给定顶点对 $s$ 和 $t$ 之间最长的简单 (即不访问重复节点) 路径的长度. 如果该图是一个道路网络, 那么最长路径的意义似乎不如最短路径那么直观 (除非你是那种总是偏好 “风景优美的路线” 的人). 但图可以且正被用于模拟各种现象, 在许多此类情况下, 寻找最长路径 (及其一些变体) 可能非常有用. 特别的, 寻找最长路径是著名的 哈密顿路径问题 的推广, 该问题要求在 $s$ 和 $t$ 之间寻找一条极大长度的简单路径 (即访问所有 $n$ 个顶点各一次的路径); 它也是臭名昭著的 旅行商问题 (TSP) 的推广, 即在带权图中寻找一条访问所有顶点且成本至多为 $w$ 的路径. TSP 是一个经典的优化问题, 其应用范围涵盖了从规划和物流到 DNA 测序和天文学的各个领域.

令人惊讶的是, 虽然我们可以在 $O(m)$ 时间内找到最短路径, 但目前还没有已知的最长路径问题算法能显著优于平凡的 “穷举搜索” 或 “暴力” 算法, 后者会枚举此类路径中所有呈指数级增长的可能性. 具体而言, 目前已知最好的最长路径问题算法对于某些常数 $c>1$ 需要 $O(c^n)$ 的时间. (目前的最好记录是 $c\sim 1.65$ 左右; 即使是获得 $O(2^n)$ 的时间界限也并非易事, 参见 习题 12.1).

12.1.3 找到图中的最小割

给定一个图 $G=(V,E),$ $G$ 的一个割为一个子集 $S\subseteq V,$ 满足 $S$ 既非空集也非 $V$ 本身. 被 $S$ 割断的边是那些一个端点在 $S$ 中, 另一个端点在 $\overline{S}=V\setminus S$ 中的边. 我们将这个边集记作 $E(S,\overline{S}).$ 如果 $s,t\in V$ 是一对顶点, 那么一个**$s,t$ 割**是指满足 $s\in S$ 且 $t\in \overline{S}$ 的割 (见图 图 12.3), 最小 $s,t$ 割问题的任务是: 给定 $s$ 和 $t,$ 找到最小的数 $k,$ 使得存在一个 $s,t$ 割恰好割断 $k$ 条边 (该问题有时也表述为找到达到这个最小值的集合; 事实证明, 计算该数目的算法通常也能给出这个集合). 形式化的, 我们定义 $MINCUT:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ 为这样一个函数: 输入一个表示三元组 $(G=(V,E),s,t)$ (即一个图及两个顶点) 的字符串, 输出最小的数 $k,$ 使得存在一个集合 $S\subseteq V,$ 满足 $s\in S,$ $t\notin S$ 且 $|E(S,\overline{S})|=k.$

计算最小 $s,t$ 割在许多应用中很有用, 因为最小割往往对应着瓶颈. 例如, 在通信网络或铁路网络中, $s$ 和 $t$ 之间的最小割对应于如果移除则会使 $s$ 与 $t$ 断开的最少边数 (这实际上是该问题的原始动机; 参见 第 12.6 节). 类似的应用出现在调度和规划中, 在 图像分割 的场景中, 我们可以定义一个图, 其顶点是像素, 边对应颜色不同的相邻像素. 如果我们想将前景与背景分离, 那么我们可以选择 (或猜测) 一个前景像素 $s$ 和一个背景像素 $t,$ 然后求它们之间的一个最小割.

计算 $MINCUT$ 的朴素算法会检查一个 $n$ 顶点图的所有 $2^n$ 个可能子集, 但事实证明我们可以做得比这好得多. 正如本书中反复看到的, 计算同一个函数可以有不止一种算法, 其中某些算法可能比其他算法更高效. 幸运的是, 最小割问题正是这种情况之一. 特别地, 我们将在下一节看到, 存在一些算法可以在顶点数的多项式时间内计算 $MINCUT.$

12.1.4 最大流最小割和线性规划

我们可以利用 最大流最小割定理 得到一个计算 $MINCUT$ 的多项式时间算法. 该定理指出, 如果每条边都具有单位容量, 则 $s$ 和 $t$ 之间的最小割等于我们可以从 $s$ 发送到 $t$ 的最大流量. 具体来说, 想象图中的每条边都对应一根管道, 每单位时间可以输送一个单位的流体 (例如每秒 1 升水). 最大 $s,t$ 流是我们可以通过这些管道从 $s$ 传输到 $t$ 的最大水量. 如果存在一个包含 $k$ 条边的 $s,t$ 割, 那么最大流至多为 $k.$ 原因是这样的割 $S$ 起到了 “瓶颈” 的作用, 因为在任何给定的单位时间内, 从 $S$ 流向其补集的流量至多为 $k$ 个单位. 这意味着最大 $s,t$ 流总是至多等于最小 $s,t$ 割的值. 最大流最小割定理中令人惊讶且非平凡的内容是, 最大流也至少等于最小割的值, 因此计算割等同于计算流.

最大流最小割定理将计算最小割的任务归约为计算最大流的任务. 然而, 这仍然没有展示如何计算这样的流. Ford-Fulkerson 算法 是一种通过增量改进直接计算流的方法. 但在多项式时间内计算流也是一种更通用的工具——线性规划 的一个特例.

具有 $m$ 条边的图 $G$ 上的流可以建模为一个向量 $x\in {\mathbb{R}}^m,$ 其中对于每条边 $e,$ $x_e$ 对应于在 $e$ 上每单位时间流过的水量. 我们将边 $e$ 视为一个有序对 $(u,v)$ (我们可以任意选择顺序), 并令 $x_e$ 为从 $u$ 流向 $v$ 的流量. (如果流向相反, 则我们将 $x_e$ 设为负值.) 由于每条边的容量为 1, 我们知道对于每条边 $e,$ 都有 $-1\le x_e\le 1.$ 一个有效的流具有以下性质: 从源点 $s$ 流出的水量与进入汇点 $t$ 的水量相同, 且对于每个其他顶点 $v,$ 进入和离开 $v$ 的水量相同.

数学上, 我们可以将这些条件写作如下形式:

$$\begin{array}{rlrl}\sum _{e\ni s}{x}_e+\sum _{e\ni t}{x}_e& =0& & \\ \sum _{e\ni v}{x}_e& =0& & {\forall }_{v\in V\setminus \{s,t\}}\\ -1\le x_e\le 1& & & {\forall }_{e\in E}\end{array}\text{\hspace{1em}(12.1)}$$

其中对于每个顶点 $v,$ 对 $e\ni v$ 求和意味着对所有与 $v$ 相连的边求和.

最大流问题可以看作是在满足上述条件 (12.1) 的所有向量 $x\in {\mathbb{R}}^m$ 中最大化 ${\sum }_{e\ni s}{x}_e$ 的任务. 在满足某些线性等式和不等式的 $x\in {\mathbb{R}}^m$ 集合上最大化线性函数 $\ell (x)$ 被称为线性规划. 幸运的是, 存在求解线性规划的 多项式时间算法, 因此我们可以在多项式时间内解决最大流 (以及等价的最小割) 问题. 事实上, 针对最大流/最小割有更好的算法, 即使是对于加权有向图, 目前的记录为 $O(\min \{m^{10/7},m\sqrt{n}\})$ 时间.

对 练习 12.1 的解答

根据上述内容, 我们知道存在一个多项式时间算法 $A,$ 它在输入 $(G,s,t)$ 时能找到图 $G$ 中的最小 $s,t$ 割. 利用 $A,$ 我们可以得到一个算法 $B,$ 在输入图 $G$ 时按如下方式计算全局最小割:

1. 对于每一对不同的 $s,t\in V,$ 算法 $B$ 设置 $k_{s,t}\leftarrow A(G,s,t).$

2. $B$ 返回所有不同对 $s,t$ 中 $k_{s,t}$ 的最小值.

$B$ 的运行时间将是 $A$ 的运行时间的 $O(n^2)$ 倍, 因此是多项式时间. 此外, 如果全局最小割是 $S,$ 那么当 $B$ 到达 $s\in S$ 且 $t\notin S$ 的迭代时, 它将获得该割的值, 因此 $B$ 输出的值将是全局最小割的值.

以上是我们第一个关于多项式时间算法背景下归约的例子. 即, 我们将计算全局最小割的任务归约为计算最小 $s,t$ 割的任务.

12.1.5 找到图中的最大割

最大割问题是指在给定图 $G=(V,E)$ 的情况下, 找到使被 $S$ 切割的边数最大化的子集 $S\subseteq V$ 的任务. (我们也可以像处理最小割那样, 为最大割定义一个 $s,t$-割变体; 这两个变体具有相似的复杂度, 但全局最大割在文献中更为常见.) 与其“亲戚”最小割问题一样, 最大割问题也有着非常强的实际动机. 例如, 最大割出现在 VLSI 设计中, 并且与统计物理学中伊辛模型的分析有着某些令人惊讶的联系.

令人惊讶的是, 尽管 (正如我们所见) 最小割问题存在多项式时间算法, 但目前还没有已知的算法能比尝试所有 $2^n$ 种 $S$ 集合可能性的平凡暴力算法更快地解决最大割问题.

12.1.6 关于凸性的说明

这是为什么在定义域上最大化和最小化一个函数的难度有时存在巨大差异的一个深层原因. 如果 $D\subseteq {\mathbb{R}}^n,$ 那么对于每一个 $x,y\in D$ 和 $p\in [0,1],$ 如果都满足 $f(px+(1-p)y)\le pf(x)+(1-p)f(y),$ 则我们称函数 $f:D\to \mathbb{R}$ 是凸的. 也就是说, $f$ 作用于 $x$ 和 $y$ 之间的 $p$-加权中点的结果, 小于 $f$ 的 $p$-加权平均值. 如果 $D$ 本身是凸的 (这意味着如果 $x,y$ 在 $D$ 中, 则它们之间的线段也在 $D$ 中), 那么这意味着如果 $x$ 是 $f$ 的局部极小值, 则它也是全局最小值. 原因是如果 $f(y)<f(x),$ 那么线段 $x$ 和 $y$ 之间的每一个点 $z=px+(1-p)y$ 都会满足 $f(z)\le pf(x)+(1-p)f(y)<f(x),$ 因此 $x$ 绝不可能是局部极小值. 直觉上, 函数的局部极小值比全局极小值容易找得多: 毕竟, 任何不断寻找值更低的附近点的 “局部搜索” 算法最终都会到达一个局部极小值. 这种局部搜索算法的一个例子是 梯度下降, 它采取一系列微小的步长, 每一步都朝着根据当前导数能最大程度降低值的方向进行.

事实上, 在某些技术条件下, 我们通常可以高效地找到凸定义域上凸函数的最小值, 这也是为什么最小割和最短路径等问题易于解决的原因. 另一方面, 在凸定义域上最大化一个凸函数 (或者等价地, 最小化一个凹函数) 通常是一项艰巨的计算任务. 线性函数既是凸的又是凹的, 这就是为什么线性函数的最大化和最小化问题都可以高效完成的原因.

最小割问题先验地并不是一个凸最小值任务, 因为潜在割的集合是离散的而不是连续的. 然而, 事实证明我们可以通过 (线性) 最大流问题将其嵌入到一个连续且凸的集合中. “最大流最小割” 定理确保了这种嵌入是 “紧” 的, 即我们通过最大流线性规划获得的最小 “分数割” 将与真实的最小割相同. 不幸的是, 我们在最大割问题的设定中没有发现有这种紧嵌入.

凸性将在高效计算的语境中一次又一次地出现. 例如, 机器学习中的基本任务之一是经验风险最小化. 这是为给定的一组训练样本寻找分类器的任务. 也就是说, 输入是一组带标签的样本 $(x_0,y_0),\dots ,(x_{m-1},y_{m-1}),$ 其中每个 $x_i\in \{0,1{\}}^n$ 且 $y_i\in \{0,1\},$ 目标是找到一个分类器 $h:\{0,1{\}}^n\to \{0,1\}$ (或者有时是 $h:\{0,1{\}}^n\to \mathbb{R})$ 以最小化错误数量. 更一般地, 我们希望找到使下式最小化的 $h:$ $$\sum _{i=0}^{m-1}L(y_i,h(x_i))$$ 其中 $L$ 是某种损失函数, 用于衡量预测标签 $h(x_i)$ 与真实标签 $y_i$ 之间的距离. 当 $L$ 是平方损失函数 $L(y,y^{\prime })=(y-y^{\prime }{)}^2$ 且 $h$ 是线性函数时, 经验风险最小化对应于众所周知的凸最小值任务: 线性回归. 在其他情况下, 当任务是非凸的时, 可能存在许多全局或局部极小值. 即便如此, 即使我们没有找到全局 (甚至局部) 极小值, 这种连续嵌入仍然可以帮助我们. 特别是在运行诸如梯度下降之类的局部改进算法时, 我们可能仍然会找到一个 “有用” 的函数 $h,$ 即在来自相同分布的未来样本上具有较小的误差.

12.2 图之外的问题

不是所有计算问题都源自于图. 接下来, 我们将会举一些其他的极受关注的计算问题.

12.2.1 SAT

一个命题公式 $\phi$ 涉及 $n$ 个变量 $x_1,\dots ,x_n$ 以及逻辑运算符 AND ($\wedge ),$ OR ($\vee )$ 和 NOT ($\neg ,$ 也记作 $\overline{\cdot }).$ 如果一个公式是若干个变量或其否定形式的 OR 运算结果的 AND, 我们称该公式为合取范式 (conjunctive normal form, 简称 CNF). 我们将 $x_i$ 或 ${\overline{x}}_i$ 这种形式的项称为文字. 例如, 这是一个 CNF 公式:

$$(x_7\vee {\overline{x}}_{22}\vee x_{15})\wedge (x_{37}\vee x_{22})\wedge (x_{55}\vee {\overline{x}}_7)$$

可满足性问题 (SAT)的任务是: 给定一个 CNF 公式 $\phi ,$ 确定是否存在一个针对 $\phi$ 的满足赋值. $\phi$ 的满足赋值是一个字符串 $x\in \{0,1{\}}^n,$ 当我们将变量赋值为 $x$ 时, $\phi$ 的计算结果为 True. SAT 问题看似只是一个仅在逻辑学中受关注的抽象问题, 但事实上, SAT 在工业优化领域具有极大的价值, 其应用包括制造规划, 电路综合, 软件验证, 空中交通管制, 运动赛事排程等等.

2SAT. 如果一个公式是若干个 OR 运算的 AND, 且每个 OR 运算恰好涉及 $k$ 个文字, 我们称其为 $k$-CNF. $k$-SAT 问题是可满足性问题在输入公式为 $k$-CNF 情况下的受限版本. 特别地, 2SAT 问题 是指: 给定一个 $2$-CNF 公式 $\phi ,$ 寻找是否存在一个赋值 $x\in \{0,1{\}}^n$ 能够满足 $\phi ,$ 即让它的计算结果为 $1$ 或 “True”. 解决 2SAT 的平凡暴力算法会枚举所有 $2^n$ 个赋值 $x\in \{0,1{\}}^n,$ 但幸运的是, 我们可以做得更好. 其关键在于, 我们可以将每个形式为 ${\ell }_i\vee {\ell }_j$ 的约束 (其中 ${\ell }_i,{\ell }_j$ 是对应变量或其否定的文字) 视为一个蕴含式 ${\overline{\ell }}_i\Rightarrow {\ell }_j,$ 因为它对应的约束是: 如果文字 ${\ell }_i^{\prime }={\overline{\ell }}_i$ 为真, 那么 ${\ell }_j$ 也必须为真. 因此, 我们可以将 $\phi$ 看作是一个在 $2n$ 个文字之间构建的有向图, 从 ${\ell }_i$ 到 ${\ell }_j$ 的边对应从前者到后者的蕴含关系. 可以证明, $\phi$ 是不可满足的, 当且仅当存在某个变量 $x_i,$ 使得图中既存在从 $x_i$ 到 ${\overline{x}}_i$ 的有向路径, 也存在从 ${\overline{x}}_i$ 到 $x_i$ 的有向路径 (参见 习题 12.2). 这便将 2SAT 归约为有向图连通性这一 (可高效解决的) 问题.

3SAT. 3SAT 问题是确定 3CNF 可满足性的任务. 人们可能会认为, 将 “2” 改为 “3” 在复杂度上不会产生太大区别. 但这种想法是错误的. 尽管付出了巨大努力, 我们目前仍未发现显著优于暴力搜索的 3SAT 算法 (目前已知最好的算法大约需要 $1.3^n$ 个步骤).

有趣的是, 类似的问题在计算领域屡见不鲜: “2” 和 “3” 之间的区别往往对应着 “易于处理” 与 “难于处理” 之间的界限. 尽管我们稍后会看到的 $\mathbf{NP}$ 完全性概念解释了一部分原因, 但我们尚不完全理解这一现象背后的原因. 这可能与优化多项式往往相当于对其导数求解方程有关. 二次多项式的导数是线性的, 而三次多项式的导数是二次的. 正如我们将看到的, 求解线性方程与求解二次方程之间的区别可能是非常深远的.

12.2.2 解线性方程组

人们一次又一次解决的最有用的问题之一, 就是求解包含 $n$ 个变量的 $n$ 个线性方程组. 即, 求解形如以下形式的方程:

$$\begin{array}{rlrlrlrl}{a}_{0,0}{x}_0& +a_{0,1}{x}_1& & +\cdots & & +a_{0,n-1}{x}_{n-1}& & =b_0\\ a_{1,0}{x}_0& +a_{1,1}{x}_1& & +\cdots & & +a_{1,n-1}{x}_{n-1}& & =b_1\\ ⋮& +⋮& & +⋮& & +⋮& & =⋮\\ a_{n-1,0}{x}_0& +a_{n-1,1}{x}_1& & +\cdots & & +a_{n-1,n-1}{x}_{n-1}& & =b_{n-1}\end{array}$$

其中 $\{a_{i,j}{\}}_{i,j\in [n]}$和$\{b_i{\}}_{i\in [n]}$ 为实数 (或有理数). 更紧凑地, 我们可以将其写成方程 $Ax=b,$ 其中 $A$ 是一个 $n\times n$ 矩阵, 且 $x,b$ 为 ${\mathbb{R}}^n$ 中的列向量.

标准的高斯消元算法可以在多项式时间内求解这类方程 (即, 判断它们是否有解, 如果有, 则找出解). 正如我们上面讨论的, 如果允许一些精度损失, 我们甚至有算法处理线性不等式, 即线性规划. 相比之下，如果我们坚持要求整数解，那么求解线性等式或不等式的任务被称为整数规划, 而已知最好的算法在最坏情况下需要指数时间.

12.2.3 解二次方程组

假设我们不仅想解线性方程, 还要处理包含形式为 $a_{i,j,k}{x}_j{x}_k$ 的二次项的方程. 即, 假设给定一组二次多项式 $p_1,\dots ,p_m,$ 并考虑方程组 $\{p_i(x)=0\}.$ 为了避免位表示的问题, 我们始终假设方程组包含约束 $\{x_i^2-x_i=0{\}}_{i\in [n]}.$ 由于只有 $0$ 和 $1$ 满足方程 $a^2-a=0,$ 这一假设意味着我们可以将注意力集中在 $\{0,1{\}}^n$ 中的解. 解多变量二次方程是一个经典且有着极强动机的问题. 它是高中生们苦苦钻研的单变量二次方程经典情况的推广. 它还推广了二次分配问题, 该问题在 20 世纪 50 年代被提出, 作为优化经济活动分配的一种方法. 同样的, 对于这个问题, 除了枚举所有 $2^n$ 种可能性的算法之外, 我们还不知道有更好的算法.

12.3 更进阶的例子

我们将列举一些更有趣的计算问题, 它们稍微复杂一些, 但在物理学, 经济学, 数论和密码学等领域具有重要意义.

12.3.1 矩阵的行列式

$n\times n$ 矩阵 $A$ 的行列式 (记作 $\det (A))$ 是线性代数中一个极其重要的量. 例如, 众所周知, $\det (A)\ne 0$ 当且仅当 $A$ 是非奇异的, 这意味着它具有逆矩阵 $A^{-1},$ 因此我们总能唯一地求解形式为 $Ax=b$ 的方程, 其中 $x$ 和 $b$ 为 $n$ 维向量. 更广泛地说, 行列式可以被视为衡量 $A$ 偏离奇异程度的一个定量指标. 如果 $A$ 的行 “几乎” 线性相关 (例如, 如果第三行非常接近前两行的线性组合), 那么行列式将很小; 而如果它们相距甚远 (例如, 如果它们彼此正交, 那么行列式将很大). 特别地, 对于每个矩阵 $A,$ 其行列式的绝对值最大不超过各行范数 (即项的平方和的平方根) 的乘积, 当且仅当各行彼此正交时取等号.

行列式可以用多种方式定义. 定义 $n\times n$ 矩阵 $A$ 行列式的一种方法是:

$$\det (A)=\sum _{\pi \in S_n}\mathrm{sign}(\pi )\prod _{i\in [n]}{A}_{i,\pi (i)}\text{\hspace{1em}(12.2)}$$

其中 $S_n$ 是从 $[n]$ 到 $[n]$ 的所有置换的集合, 且置换 $\pi$ 的符号 等于 $-1$ 的 $\pi$ 中逆序对数量次方 (逆序对是指满足 $i>j$ 但 $\pi (i)<\pi (j)$ 的二元组 $i,j).$

这个定义表明计算 $\det (A)$ 可能需要对 $|S_n|$ 个项求和, 这将耗费指数级时间, 因为 $|S_n|=n!>2^n.$ 然而, 还有其他计算行列式的方法. 例如, 众所周知 $\det$ 是唯一满足以下条件的函数:

1. 对于每个方阵 $A,B,$ 有 $\det (AB)=\det (A)\det (B).$

2. 对于每个对角线项为 $d_0,\dots ,d_{n-1}$ 的 $n\times n$ 三角矩阵 $T,$ 有 $\det (T)={\prod }_{i=0}^n{d}_i.$ 特别地, $\det (I)=1,$ 其中 $I$ 是单位矩阵. (三角矩阵是指主对角线下方或上方的所有项均为零的矩阵.)

3. $\det (S)=-1,$ 其中 $S$ 是对应于交换 $I$ 的两行或两列的 “交换矩阵”. 也就是说, 存在两个坐标 $a,b,$ 使得对于每个 $i,j:$ $S_{i,j}=\{\begin{array}{ll}1& i=j,i\notin \{a,b\}\\ 1& \{i,j\}=\{a,b\}\\ 0& \text{otherwise}\end{array}.$

利用这些规则和高斯消元算法, 可以判断 $A$ 是否为奇异矩阵, 如果不是, 则将 $A$ 分解为多项式数量个交换矩阵和三角矩阵的乘积. (事实上, 可以验证高斯消元中的行操作对应于乘以交换矩阵或三角矩阵.) 因此, 我们可以使用多项式时间的算术运算来计算 $n\times n$ 矩阵的行列式.

12.3.2 矩阵的积和式

给定一个 $n\times n$ 的矩阵 $A,$ $A$ 的积和式定义为

$$\mathrm{perm}(A)=\sum _{\pi \in S_n}\prod _{i\in [n]}{A}_{i,\pi (i)}.\text{\hspace{1em}(12.3)}$$

也就是说, $\mathrm{perm}(A)$ 的定义与 (12.2) 中的行列式类似, 区别在于我们去掉了 $\mathrm{sign}(\pi )$ 这一项. 矩阵的积和式是一个自然存在的量, 并在包括组合数学和图论在内的多个领域中得到了研究. 它也出现在物理学中, 可用于描述多个玻色子颗粒的量子态 (参见 此处 和 此处).

模 2 下的积和式. 如果 $A$ 的元素是整数, 那么我们可以定义一个 布尔 函数 $per{m}_2,$ 它在输入矩阵 $A$ 时输出 $A$ 的积和式模 $2$ 的结果. 事实证明, 我们可以在多项式时间内计算 $per{m}_2(A).$ 其关键在于在模 $2$ 运算下, $-x$ 和 $+x$ 是相等的量; 因此, 既然 (12.2) 和 (12.3) 之间的唯一区别只是某些项乘以了 $-1,$ 那么对于每一个 $A,$ 都有 $\det (A)\mathrm{mod}2=\mathrm{perm}(A)\mathrm{mod}2.$

模 3 下的积和式. 受到上面好运的鼓舞, 我们或许希望能够计算模任何素数 $p$ 的积和式, 甚至是在一般情况下的结果. 但很可惜, 我们没有那样的运气. 在类似于 “从 2 到 3” 的现象中, 我们目前还不知道有什么比暴力搜索好得多的算法, 甚至连快速计算模 $3$ 的积和式都做不到.

12.3.3 寻找零和博弈平衡

零和博弈 是指两个玩家之间的博弈, 其中一个玩家的收益等于另一个玩家的惩罚. 也就是说, 无论第一名玩家获得什么, 第二名玩家都会失去相同的部分. 尽管我们都想避开它们, 但零和博弈在现实生活中确实存在, 而它们唯一的好处在于我们至少可以计算出最优策略.

一个零和博弈可以用一个 $n\times n$ 的矩阵 $A$ 来表示, 如果玩家 1 选择动作 $i$ 且玩家 2 选择动作 $j,$ 那么玩家 1 获得 $A_{i,j},$ 而玩家 2 失去相同的金额. 约翰·冯·诺依曼的著名的 极小极大定理 指出, 如果我们允许概率性的或 “混合” 策略 (即玩家不选择单一动作, 而是选择动作上的一个分布), 那么谁先行动并不重要: 最终结果将是一样的. 从数学上讲, 极小极大定理是指, 如果我们令 ${\Delta }_n$ 为 $[n]$ 上的概率分布集合 (即 ${\mathbb{R}}^n$ 中元素之和为 $1$ 的非负列向量), 那么

$$\underset{p\in {\Delta }_n}{\max }\underset{q\in {\Delta }_n}{\min }{p}^{\top }Aq=\underset{q\in {\Delta }_n}{\min }\underset{p\in {\Delta }_n}{\max }{p}^{\top }Aq\text{\hspace{1em}(12.4)}$$

极小极大定理被证明是线性规划对偶性的一个推论, 事实上, (12.4) 的值可以通过线性规划高效地计算出来.

12.3.4 寻找纳什均衡

幸运的是, 并非所有现实世界的博弈都是零和博弈. 我们确实有更通用的博弈模型, 其中一名玩家的收益并不一定等于另一名玩家的损失. 约翰·纳什 因证明了此类博弈也存在 “均衡” 概念而获得了诺贝尔奖. 在许多经济学文献中, 人们坚信当真实的代理人参与此类博弈时, 他们最终会达到纳什均衡. 然而, 与零和博弈不同, 我们目前还不知道在给定通用 (非零和) 博弈描述的情况下, 寻找纳什均衡的高效算法. 特别的, 这意味着尽管经济学家有直觉感悟, 但仍存在某些博弈, 其自然策略需要指数级步数才能收敛到均衡状态.

12.3.5 素性测试

另一个经典的计算问题——自古希腊时代起就引起了人们的兴趣——是判断给定的数字 $N$ 是素数还是合数. 显而易见, 我们可以通过尝试用 $2,\dots ,N-1$ 中的所有数字去除它来做到这一点, 但这将至多花费 $N$ 步, 就其位复杂度 $n=\log N$ 而言, 这是 “指数级” 的. 我们可以通过观察发现, 如果 $N$ 是形式为 $N=PQ$ 的合数, 那么 $P$ 或 $Q$ 必有一个小于 $\sqrt{N},$ 从而将这 $N$ 步减少到 $\sqrt{N},$ 但这仍然相当糟糕. 如果 $N$ 是一个 $1024$ 位的整数, $\sqrt{N}$ 大约是 $2^{512},$ 因此在这样的输入上运行该算法所花费的时间将远超宇宙的寿命.

幸运的是, 事实证明我们可以做得更好. 在 20 世纪 70 年代, Rabin 和 Miller 提出了 “概率性” 算法 ², 可以在 $poly(n)$ 时间内 (其中 $n=\log N)$ 确定给定数字 $N$ 是素数还是合数. 我们将在本课程稍后讨论计算的概率模型. 2002 年, Agrawal, Kayal 和 Saxena 发现了该问题的一个确定性 $poly(n)$ 时间算法 ³. 这无疑是一个令从阿基米德到高斯的数学家们都会感到兴奋的进展.

12.3.6 整数分解

既然我们可以高效地判断一个数字 $N$ 是素数还是合数, 我们可能会期望在后一种情况下, 我们也能高效地找到 $N$ 的因数分解. 但不幸的是, 我们目前还没有发现这样的算法. 不过, 这也带来了好的消息, 这种算法的 “不存在性” 已被用作加密的基础, 实际上它构成了万维网大部分安全性的基石 ⁴. 我们将在本课程稍后回到分解问题. 我们注意到, 对于这个问题, 我们确实知道比暴力破解好得多的算法. 虽然暴力算法需要 $2^{\Omega (n)}$ 的时间来分解一个 $n$ 位整数, 但已知算法的运行时间大约为 $2^{O(\sqrt{n})},$ 并且还有被广泛认为 (尽管尚未得到完全严格的分析) 运行时间大约为 $2^{O(n^{1/3})}$ 的算法. (这里的 “大约” 是指我们忽略了关于 $n$ 的多项式对数因子.)

12.4 我们的已学内容

指数时间算法与多项式时间算法之间的区别看似只是 “量化” 的, 但实际上具有极其重要的意义. 正如我们已经看到的, 暴力指数时间算法会非常迅速地耗尽动力, 正如 Edmonds 所说, 在实践中, 一个最优算法为指数级的问题与一个完全不可解的问题之间可能没有太大区别. 因此, 我们上面提到的高效算法被广泛使用, 并为许多计算机科学应用提供动力. 此外, 多项式时间算法通常源于对当前问题的深刻洞察, 无论是 “最大流最小割” 结论, 行列式的可解性, 还是支持素性测试的群论结构. 无论其计算意义如何, 这种洞察力都是非常有用的.

目前, 我们还不知道那些 “困难” 问题是真正的困难, 还是仅仅因为我们还没有找到适合它们的算法. 然而, 我们现在将看到, 确实存在一些 “本质上需要” 指数级时间的问题. 我们只是不知道上述例子中是否有任何一个属于这一类.

12.5 习题

12.6 文献注释

经典的本科生算法入门教材是 (Cormen, Leiserson, Rivest, Stein, 2009). 两本没那么 “百科全书式” 的教材分别是 Kleinberg 和 Tardos 的 (Kleinberg, Tardos, 2006), 以及 Dasgupta, Papadimitriou 和 Vazirani 的 (Dasgupta, Papadimitriou, Vazirani, 2008). Jeff Erickson 的著作 是一本优秀的算法教材, 可以在网上免费获取.

最小割问题的起源可以追溯到冷战时期. 具体而言, Ford 和 Fulkerson 在 1955 年发现了他们的最大流/最小割算法, 当时是为了找出将俄罗斯与欧洲其他地区断开连接所需炸毁的最少铁轨数量. 更多信息请参阅综述 (Schrijver, 2005).

(Williams, 2009) (Bjorklund, 2014) 中给出了一些针对最长路径问题的算法.

12.7 进一步探索

与本章相关, 高年级学生可能会感兴趣的一些主题包括: (待补充)

---

1: 队列 是一种以 “先进先出 (FIFO)” 顺序存储元素列表的数据结构。每次 “出队” 操作都会按照元素 “入队” 的顺序将其移出; 参见 Wikipedia 页面.

2: Miller-Rabin 素性测试

3: AKS 素性测试

4: RSA 加密算法

5: 提示: 使用动态规划, 对每个 $s,t\in [n]$ 以及 $S\subseteq [n],$ 计算值 $P(s,t,S).$ 如果存在一条恰好经过集合 $S$ 中所有顶点的从 $s$ 到 $t$ 的简单路径, 则该值为 $1.$ 对大小递增的集合 $S$ 迭代执行此操作.