2. 归约¶
2.1. 归约¶
本模块介绍一个用于理解问题之间关系的重要概念，称为 归约。 归约使我们能够借助另一个问题来求解一个问题。 同样重要的是，当我们希望理解一个问题的难度时，归约使我们能够就一个问题（而非算法或程序）代价的上界和下界作出相对的陈述。
因为本章将详细讨论"问题"这一概念，我们希望用记法使问题描述更清晰。 在本章中，一个问题将用输入与输出之间的映射来定义，问题的名称全部用大写字母给出。 因此，在我们的记法中，排序问题的完整定义可以如下所示：
2.1.1. 例：配对问题¶
当你购买或编写一个程序来解决某个问题（例如排序）时，你或许能用它来帮助解决另一个不同的问题。 这在软件工程中被称为 软件复用。 为了说明这一点，让我们考虑另一个问题。
图 25.2.1 说明了 PAIRING。 求解 PAIRING 的一种方法是使用现有的排序程序对两个序列分别排序，然后按它们在有序排列中的位置进行配对。 严格地说，在这个解法中， PAIRING 被 归约 为 SORTING ，因为 SORTING 被用来求解 PAIRING 。 接下来的幻灯片详细展示了这一过程，以便你能看到任何归约中都必需的步骤。
请注意，归约是一个三步过程。 第一步是把 PAIRING 的一个实例转换为 SORTING 的两个实例。 本例中的转换步骤并不引人入胜；它只是把每个序列取出并分配给一个数组，传递给 SORTING。 第二步是对两个数组进行排序（即对每个数组应用 SORTING）。 第三步是把 SORTING 的输出转换成 PAIRING 的输出。 做法是把排序后数组中的第一个元素配对、第二个元素配对，依此类推。
把 PAIRING 归约为 SORTING 有助于建立 PAIRING 代价的上界。 从渐近记法的角度来说，假设我们能找到一种方法"足够快"地把 PAIRING 的输入转换为 SORTING 的输入， 并能找到第二种方法"足够快"地把 SORTING 的结果转换回 PAIRING 的正确结果， 那么 PAIRING 的渐近代价不可能超过 SORTING 的代价。 在本例中，从 PAIRING 转换到 SORTING ， 或把 SORTING 的答案转换回 PAIRING 的答案，几乎不需要做任何工作， 因此该解法的主要代价在于执行排序操作。 于是，PAIRING 的一个上界为 \(O(n \log n)\)。
2.2. 归约与寻找下界¶
必须指出，配对问题并 不 要求对两个序列的元素进行排序。 这只是解决问题的一种可能方式。 PAIRING 只要求序列的元素被正确配对。 也许还有别的做法呢？ 当然，如果我们用排序来求解 PAIRING，算法将需要 \(\Omega(n \log n)\) 时间。 但可以想象，另一种方法可能更快。
除了把旧算法用于求解新问题（从而为新问题建立上界）之外，归约还有另一个用途。 那就是通过说明一个新问题可以被用作某个已知下界的旧问题的解法，来证明该新问题代价的下界。 这可能是一个不太好理解的概念。 但它对于以后理解 NP 完全性来说绝对至关重要。
假设我们可以反方向进行，把 SORTING "足够快"地转换为 PAIRING 。 这对于 PAIRING 的最小代价意味着什么？ 我们知道，SORTING 在最坏情况和平均情况下的 下界 为 \(\Omega(n \log n)\)。 换句话说，排序的最佳可能算法至少需要 \(n \log n\) 时间。
假设 PAIRING 可以在 \(O(n)\) 时间内完成。 那么，构造排序算法的一种方法就是把 SORTING 转换为 PAIRING ，运行 PAIRING 的算法， 最后把答案转换回 SORTING 的答案。 只要我们能"足够快"地在 SORTING 与 PAIRING 之间相互转换， 这一过程就会给出一个 \(O(n)\) 的排序算法！ 因为这与我们所知的 SORTING 下界相矛盾，而推理中唯一的缺陷正是"PAIRING 可在 \(O(n)\) 时间内完成"这一初始假设， 所以我们可以得出结论：PAIRING 不存在 \(O(n)\) 时间算法。 这一归约过程告诉我们， PAIRING 至少必须和 SORTING 一样昂贵， 因此它本身也必定有 \(\Omega(n \log n)\) 的下界。
为了完成关于 PAIRING 下界的证明，我们现在需要找到一种将 SORTING 归约到 PAIRING 的方法。这很容易做到。取一个 SORTING 实例（即一个包含 \(n\) 个元素的数组 \(A\) ）。生成第二个数组 \(B\) ，它仅在位置 \(i\) 存储 \(i\) ，其中 \(0 \leq i < n\) 。将这两个数组传递给 PAIRING 。取结果得到的配对集合，并使用配对中 \(B\) 部分的值来指示 \(A\) 部分在排序数组中应占据的位置；也就是说，我们现在可以使用 \(B\) 数组中的对应值作为排序键，对 \(A\) 数组中的记录重新排序，并运行一个简单的 \(\Theta(n)\) Binsort 。将 SORTING 转换为 PAIRING 可以在 \(O(n)\) 时间内完成，同样地，将 PAIRING 的输出转换为 SORTING 的正确输出也可以在 \(O(n)\) 时间内完成。因此，该“排序算法”的成本由 PAIRING 的成本主导。
2.3. 归约模板¶
在详细展示把 SORTING 归约为 PAIRING 的示例之前，让我们先退一步， 确保我们理解了以归约模板（Reduction Template）来定义这一过程的总体流程。
考虑任意两个我们能找到合适归约的问题：从其中一个到另一个。 第一个问题接受其任意输入实例（我们称之为 I ），并把 I 转换为一个解（我们称之为 SLN ）。 第二个问题接受其任意输入实例（我们称之为 I' ），并把 I' 转换为一个解（我们称之为 SLN' ）。 我们可以更正式地把归约定义为一个三步过程：
把第一个问题的任意实例转换为第二个问题的一个实例。 换句话说，必须存在从第一个问题的任何实例 I 到第二个问题实例 I' 的转换。
对实例 I' 应用第二个问题的算法，得到解 SLN' 。
把 SLN' 转换为 I 的解（称为 SLN ）。 注意，要使归约成立， SLN 实际上必须是 I 的正确解。
下面的练习给你一个机会，让你重现基本的归约证明过程。 这将有助于确认你是否理解这一过程。
2.4. PAIRING 的下界¶
接下来是一个幻灯片，展示把 SORTING 归约为 PAIRING 的各个步骤。
必须指出，归约过程本身并不给我们求解任一问题的算法。 它只是给了我们一个方法：在已经拥有第二个问题的解的前提下求解第一个问题。 对于本章其余部分将要讨论的主题更重要的是，归约给了我们一种以另一个问题的视角来理解一个问题界的方式。 具体来说，在给定高效转换的前提下，第一个问题的上界至多是第二个问题的上界； 反过来，第二个问题的下界至少是第一个问题的下界。 这些都不需要知道任一问题的实际解。 这尤其有用，因为我们经常使用归约来证明某物不存在（或至少运行不快）。
下面的练习给你一个机会，让你重现把 SORTING 归约为 PAIRING。 这将有助于确认你是否理解这一过程。
2.5. 两个乘法例子¶
作为归约的第二个例子，考虑两个 \(n\) 位数相乘这个简单的问题。 标准的竖式乘法是这样做的：把第一个数的末位数字乘以第二个数（需 \(\Theta(n)\) 时间）， 把第一个数的第二位数字乘以第二个数（再次需要 \(\Theta(n)\) 时间）， 依此类推，直到第一个数的 \(n\) 个数字全部处理完。 最后，把各个中间结果相加。 注意，把长度为 \(M\) 和 \(N\) 的两个数相加，很容易在 \(\Theta(M + N)\) 时间内完成。 由于第一个数的每个数字都要与第二个数的每个数字相乘，该算法需要 \(\Theta(n^2)\) 时间。 已知有渐近更快（但更复杂）的算法，但没有一个快到属于 \(O(n)\)。
接下来我们提出一个问题： 对一个 \(n\) 位数求平方，与两个 \(n\) 位数相乘一样困难吗？ 我们或许希望这种特殊情况中的某些性质能带来比更一般的乘法问题所需算法更快的算法。 然而，一个简单的归约证明足以表明：求平方与相乘一样"困难"。
归约的关键在于下面的公式：
这个公式的意义在于，它使我们能把任意一个乘法实例转换为一系列操作， 包括三次加减法（每次都能在线性时间内完成）、两次平方以及一次除以 4。 这是因为
注意，除以 4 可以在线性时间内完成（只需转换成二进制，右移两位，再转换回来）。 这个归约表明：如果能找到求平方的线性时间算法，就可以用它构造乘法的线性时间算法。
我们的下一个归约例子涉及两个 \(n \times n\) 矩阵相乘。
对于这个问题，我们假设矩阵中存储的值是简单整数，并且两个简单整数相乘需要常数时间
（因为两个 int 变量的相乘需要固定数量的机器指令）。
两个矩阵相乘的标准算法是把第一个矩阵第一行的每个元素与第二个矩阵第一列的相应元素相乘，然后把这些数相加。
这需要 \(\Theta(n)\) 时间。
解的 \(n^2\) 个元素都以类似方式计算，总共需要 \(\Theta(n^3)\) 时间。
已知有更快的算法
（参见
Strassen 算法），
但没有一个快到属于 \(O(n^2)\)。
现在，考虑两个 对称矩阵 相乘的情况。 对称矩阵是一种第 \(ij\) 项等于第 \(ji\) 项的矩阵； 也就是说，矩阵的右上三角是左下三角的镜像。 在这种受限情况下，是否有某种性质能让我们比一般情况更快地相乘两个对称矩阵？ 答案是否定的，如下面的归约所示。 假设给定两个 \(n \times n\) 矩阵 \(A\) 和 \(B\)。 我们可按如下方式从任意矩阵 \(A\) 构造一个 \(2n \times 2n\) 对称矩阵：
这里 0 表示由零值组成的 \(n \times n\) 矩阵，\(A\) 是原矩阵，\(A^{\rm T}\) 表示矩阵 \(A\) 的转置。 （转置操作把原矩阵的位置 \(ij\) 放到转置矩阵的位置 \(ji\)。 对于一个 \(n \times n\) 矩阵，这很容易在 \(n^2\) 时间内完成。）
注意，得到的矩阵现在是对称的。 我们也可以用类似的方式把矩阵 \(B\) 转换为对称矩阵。 如果对称矩阵能被"快速"相乘（特别是，如果它们能在 \(\Theta(n^2)\) 时间内相乘）， 那么我们就能利用以下观察结果，在 \(\Theta(n^2)\) 时间内求出两个任意 \(n \times n\) 矩阵相乘的结果：
在上面的公式中，\(AB\) 是矩阵 \(A\) 与 \(B\) 相乘的结果。
下面的幻灯片展示了这一归约过程。
2.6. 界的定理¶
记法 \(\leq_{O(g(n))}\) 表示归约可以借助代价为 \(O(g(n))\) 的转换来完成。
下界定理：如果 \(P_1 \leq_{O(g(n))} P_2\)， 且 \(P_1\) 的时间复杂度存在下界 \(\Omega(h(n))\)， 而 \(g(n) = o(h(n))\)， 那么 \(P_2\) 的时间复杂度也存在下界 \(\Omega(h(n))\)。 （注意是小 o，不是大 O。意思是前者确实比后者小。）
例： SORTING \(\leq_{O(n)}\) PAIRING ，因为 \(g(n) = n\)，\(h(n) = n \log n\)，且 \(g(n) = o(h(n))\)。 下界定理给出 PAIRING 的一个 \(\Omega(n \log n)\) 下界。
反过来也成立。
上界定理：如果 \(P_2\) 的时间复杂度为 \(O(h(n))\)， 且 \(P_1 \leq_{O(g(n))} P_2\)， 那么 \(P_1\) 的时间复杂度为 \(O(g(n) + h(n))\)。
因此，在给定良好转换的前提下，两个问题的运行时间至少为 \(\Omega(P_1)\)，至多为 \(O(P_2)\)。
2.7. 构造简单多边形的代价¶
SIMPLE POLYGON（简单多边形）：给定平面上的 \(n\) 个点，求以这些点为顶点的简单多边形。 （这里的"simple（简单）"指没有任何线相交。） 我们将证明 SORTING \(\leq_{O(n)}\) SIMPLE POLYGON 。
我们从 SORTING 的一个实例开始：\(\{x_1, x_2, \cdots, x_n\}\)。 在线性时间内求出 \(M = \max|x_i|\)。 设 \(C\) 为以原点为圆心、半径为 \(M\) 的圆。
我们将通过把待排序数组中的每个值替换为如下定义的相应点，来生成 SIMPLE POLYGON 的一个实例
所有这些点都落在 \(C\) 上是一个重要的事实。 此外，当我们找到简单多边形时，这些点都按排序顺序落在圆上。 这是因为以 \(C\) 上的所有点为顶点的唯一简单多边形是凸多边形。 因此，根据下界定理，SIMPLE POLYGON 属于 \(\Omega(n \log n)\)。
下面的练习给你一个机会，让你重现 SIMPLE POLYGON 至少与 SORTING 一样昂贵的证明。 这将有助于确认你是否理解这一过程。
