普林斯顿算法讲义（四）（4）

普林斯顿算法讲义（四）（3）https://developer.aliyun.com/article/1484181

应对难解性。

NP 完全性理论表明，除非 P = NP，否则有一些重要问题无法创建同时实现以下三个属性的算法：

• 保证在多项式时间内解决问题。
  
• 保证解决问题的最优性。
  
• 保证解决问题的任意实例。
  

当我们遇到 NP 完全问题时，我们必须放宽三个要求中的一个。我们将考虑解决放宽了三个目标之一的 TSP 问题的解决方案。

复杂性理论处理最坏情况的行为。这留下了设计算法的可能性，这些算法在某些实例上运行速度快，但在其他实例上需要大量时间。例如，Chaff是一个可以解决许多具有 10,000 个变量的实际 SAT 实例的程序。令人惊讶的是，它是由普林斯顿大学的两名本科生开发的。该算法不能保证在多项式时间内运行，但我们感兴趣的实例可能是“简单的”。

有时我们可能愿意牺牲找到最优解的保证。许多启发式技术（模拟退火、遗传算法、Metropolis 算法）已被设计用于找到“几乎最优”的解决方案。有时甚至可以证明最终解决方案的优良程度。例如，Sanjeev Arora 设计了一种近似算法用于欧几里德 TSP 问题，保证找到的解决方案的成本最多比最优解高 1%。设计近似算法是一个活跃的研究领域。不幸的是，也有一些不可近似性结果，即：如果您可以为问题 X 找到一个近似算法，保证可以达到最优解的 2 倍，则 P = NP。因此，为一些 NP 完全问题设计近似算法是不可能的。

如果我们试图解决 TSP 问题的特殊类，例如，点位于圆的边界上或 M×N 格点的顶点上，则我们可以设计高效（且平凡）的算法来解决问题。

利用难解性。 有时难解性问题是一件好事。在第 XYZ 节中，我们将利用难解性问题设计密码系统。

介于 P 和 NP 完全之间。 现在已知大多数 NP 中的自然问题属于 P 或 NP 完全。如果 P != NP，则可以证明有一些 NP 问题既不属于 P 也不属于 NP 完全。就像“我们还没有观察手段的暗物质”。在地下世界中有一些显著的未分类问题：因子分解和子图同构。

• 因子分解。 已知的最佳算法是 2^O(n¹/3 polylog(n)) - 数域筛法。专家认为不属于 P。
  
• 受限优先级的 3 处理器调度。 给定一组单位长度的任务和一个优先级顺序，在 3 台并行机器上找到最短的调度。
  
• 转角问题。 给定 N(N-1)/2 个正数（不一定不同），是否存在一组 N 个点在直线上，使得这些数字是 N 个点的两两距离。直觉：点是 I-95 上的出口。问题首次出现在 1930 年代的 X 射线晶体学背景中。在分子生物学中也被称为部分消化问题。
  
• 布尔公式对偶化。 给定一个单调 CNF 公式和一个单调 DNF 公式，它们是否等价？(a + b)(c + d) = ac + ad + bc + bd。简单地应用德摩根定律会导致指数级算法，因为存在冗余。最佳算法为 O(n^(log n / log log n))。
  
• 随机游戏。 白色、黑色和自然轮流在有向图的边上移动一个令牌，从起始状态 s 开始。白色的目标是将令牌移动到目标状态 t。黑色的目标是阻止令牌到达 t。自然以随机方式移动令牌。给定一个有向图、一个起始状态 s 和一个目标状态 t，白色是否有一种策略使得令牌到达 t 的概率 ≥ 1/2？该问题属于 NP 交 co-NP，但尚不清楚是否属于 P。人们相信它属于 P，只是我们还没有找到一个多项式时间算法。
  

其他复杂度类。

复杂度类 P、NP 和 NP-完全是三个最著名的复杂度类。Scott Aaronson 的网站The Complexity Zoo包含了其他复杂度类的全面列表，这些类对问题根据其计算资源（时间、空间、可并行性、随机性使用、量子计算）进行分类。我们在下面描述了一些最重要的类。

• PSPACE.复杂度类 PSPACE = 可以使用多项式空间的图灵机解决的问题。PSPACE-完全 = 在 PSPACE 中，且可以在多项式时间内将所有其他问题归约为它。

• 这里是停机问题的一个复杂版本。给定一个被限制在 n 个磁带单元上的图灵机，在最多 k 步内是否会停机？该问题是 PSPACE-完全的，其中 n 以一元编码。这意味着除非 P = PSPACE，否则我们不太可能能够判断一个给定程序在具有 n 个内存单元的计算机上运行是否会在 k 步之前终止，比简单地运行它 k 步并观察发生的情况要快得多。
  
• Bodlaender：给定一个具有顶点 1, …, N 的图，两名玩家轮流标记顶点为红色、绿色或蓝色。第一个标记一个与其邻居相同颜色的顶点的玩家失败。确定第一个玩家是否有获胜策略是 PSPACE-完全的。
  
• 许多传统游戏的变体被证明是棘手的；这在一定程度上解释了它们的吸引力。此外，黑白棋、六角、地理、上海、赛车、五子棋、瞬间疯狂和推箱子的自然推广都是 PSPACE-完全的。
  Eppstein 的困难游戏列表。
  
• 一个给定的字符串是否是上下文敏感文法的成员？
  
• 两个正则表达式是否描述不同的语言？即使在二进制字母表上也是 PSPACE-完全的，如果其中一个正则表达式是.*。
  
• 另一个可以严格化的例子是移动一个复杂对象（例如家具），其附件可以通过不规则形状的走廊移动和旋转。
  
• 另一个例子出现在并行计算中，当挑战是确定在一个通信处理器系统中是否可能存在死锁状态时。
  

• 注意 PSPACE = NPSPACE（Savitch 定理）。
  
• EXPTIME.复杂度类 EXPTIME = 所有在确定性图灵机上以指数时间可解决的决策问题。注意 P ⊆ NP ⊆ PSPACE ⊆ EXPTIME，并且根据时间层次定理，至少有一个包含是严格的，但不知道是哪一个（或多个）。有人推测所有包含都是严格的。

• Harel 的 Roadblock 第 85 页。
  
• 国际象棋、跳棋、围棋（采用日本式劫争终结规则）和将棋的自然泛化都是 EXPTIME 完全问题。给定一个棋盘局面，第一位玩家能否强迫获胜？这里 N 是棋盘大小，运行时间与 N 呈指数关系。这些问题比奥赛罗（和其他 PSPACE 完全游戏）在理论上更难的一个原因是它们可能需要指数次数的移动。跳棋（在 N×N 棋盘上的英式跳棋）：玩家在某一回合可以有指数次数的移动，因为可以进行跳跃序列。[pdf] 注意：根据终结规则的不同，跳棋可能是 PSPACE 完全或 EXPTIME 完全。对于 EXPTIME 完全，我们假设“强制捕获规则”，即如果有可用的跳跃（或跳跃序列），玩家必须进行跳跃。
  
• 这是停机问题的一个复杂性版本。给定一个图灵机，在最多 k 步内是否会停机？或者，给定一个固定的 Java 程序和一个固定的输入，在最多 k 步内是否会终止？这个问题是 EXPTIME 完全的。这里的运行时间与 k 的二进制表示成指数关系。事实上，没有图灵机可以保证在 O(k / log k)步内解决它。因此，暴力模拟基本上是最佳的方法：可以证明，这个问题不能比运行图灵机的前 k 步并观察发生了什么更快地解决。
  

• 一个 EXPTIME 完全问题在确定性图灵机上不能在多项式时间内解决 - 这与 P ≠ NP 猜想无关。
  
• EXPSPACE. EXPSPACE 完全问题：给定两个“扩展”正则表达式，它们是否表示不同的语言？通过扩展，我们允许一个平方操作（表达式的两个副本）。Stockmeyer 和 Meyer（1973）。或者更简单的集合交集（Hunt，1973）。阿贝尔群的字问题（Cardoza，Lipton，Meyer，1976），向量加法子系统。
  向量加法子系统是 EXPSAPCE 难题：给定一个非负向量 s 和一组任意向量 v1、v2、…、vn，如果向量 x 是从 s 可达的，则它要么是（i）向量 s，要么是可达的向量 y + vi，其中 y 是可达的。VAS 问题是确定给定向量 x 是否可达。
  
• DOUBLE-EXPTIME. DOUBLE-EXPTIME 类是在双指数时间内可解决的所有决策问题。一个显著的例子是确定first order Presburger arithmetic中的一个公式是否为真。Presburger 算术包括涉及只有+作为操作的整数的语句（没有乘法或除法）。它可以模拟以下语句：如果 x 和 y 是整数，使得 x ≤ y + 2，则 y + 3 > x。1929 年，Presburger 证明了他的系统是一致的（不能证明矛盾，比如 1 > 2）和完备的（每个语句都可以被证明为真或假）。1974 年，Fischer 和 Rabin 证明了任何决定 Presburger 公式真实性的算法都需要至少 2⁽⁽²(cN)))时间，其中 c 是一个常数，N 是公式的长度。
  
• 非初等. 对于任何有限的塔，超过 2²²^…²N。给定允许平方和补集的两个正则表达式，它们是否描述不同的语言？
  

其他类型的计算问题。

我们专注于搜索问题，因为这是科学家和工程师非常丰富和重要的问题类别。

• 搜索问题. 这是我们详细考虑的版本。技术上，FP = 多项式时间函数问题，FNP = 非确定性图灵机上的多项式时间函数问题。FP 问题可以有任何可以在多项式时间内计算的输出（例如，两个数字相乘或找到 Ax = b 的解）。
  
• 决策问题。 传统上，复杂性理论是以是/否问题来定义的，例如，Ax &le b 是否存在解？规约的定义更清晰（无需处理输出）。P 类和 NP 类传统上是以决策问题来定义的。通常搜索问题归约为决策问题（对于所有 NP 完全问题都已知为真）。这样的搜索问题被称为自可归约。P = NP 问题等价于 FP = FNP 问题。
  
• 全函数。有时，一个决策问题很容易，而相应的搜索问题（被认为）很难。例如，可能有一个定理断言解肯定存在，但该定理并未提供如何高效找到解的任何提示。

• 子集和示例。给定 N 个数字，找出这些 N 个数字的两个（不相交）子集，使它们的和恰好相等。如果 N = 77，且所有数字最多为二十一位十进制数，则根据鸽巢原理，至少有两个子集的和相等。这是因为有 2⁷⁷ 个子集，但最多有 1 + 77 * 10²¹ < 2⁷⁷ 种可能的和。或者决策 = 复合，搜索 = 因子。
  
• 约翰·纳什证明了在具有指定效用的两个或更多玩家的正常形式游戏中，纳什均衡总是存在。证明是非构造性的，因此不清楚如何找到这样的均衡。被证明是PPAD-完全 - 已知具有解的问题的 NP-完全问题的类比。
  
• 广义均衡理论是微观经济学的基础。给定一个有 k 种商品的经济体，每个 N 个代理人都有这些商品的初始禀赋。每个代理人还为每种商品有一个效用函数。阿罗-德布鲁定理断言，在适当的技术条件下（例如，效用函数连续、单调且严格凹），存在一组（唯一的）市场价格，使得每个代理人都卖掉所有商品，并用这笔钱购买最佳组合（即，每种商品的供求平衡）。但市场是如何计算的呢？证明依赖于拓扑学中的一个深刻定理（卡库塔尼不动点定理），目前尚不知道任何有效的算法。经济学家假设市场找到了均衡价格；亚当·斯密用看不见的手的比喻来描述这种社会机制。
  
• 15-滑块拼图的推广。测试解是否存在在 P 中，但找到最短解是棘手的。[Ratner-Warmuth, 1990]
  

• 优化问题。 有时我们有优化问题，例如，TSP。给定一个 NP 问题和一个解的成本函数，对于给定的实例，目标是找到其最佳解（例如找到最短的 TSP 旅行路线，最小能量配置等）。有时很难表述为搜索问题（找到最短的 TSP 旅行路线），因为不清楚如何有效地检查是否有最优路线。相反，我们重新表述为：给定长度 L，找到长度最多为 L 的旅行路线。然后二分搜索最优 L。
  
• 计数问题。 给定一个 NP 问题，找出其解的数量。例如，给定一个 CNF 公式，它有多少满足的赋值？包括统计物理和组合数学中的许多问题。从形式上讲，这类问题被称为#P。
  
• 战略问题。 给定一个游戏，为玩家找到一个最佳策略（或最佳移动）。包括经济学和棋盘游戏中的许多问题（例如，国际象棋，围棋）。
  

输出多项式时间。

有些问题涉及的输出比单个位的信息更多。例如，输出汉诺塔问题的解至���需要 2^N 步。这个要求不是因为解本质上难以计算，而是因为有 2^N 个输出符号，并且每个输出符号需要一个单位的时间来写入。也许更自然的衡量效率的方法是输入大小和输出大小的函数。一个具有 DFAs 的经典电气工程问题是从 RE 构建一个使用最少状态的 DFA。我们希望的算法在输入 RE 的大小（符号数量）和输出 DFA 的大小（状态数量）上都是多项式的。除非 P = NP，否则设计这样的算法是不可能的。事实上，甚至不可能设计一个在常数（甚至多项式）数量的状态内得出答案的多项式算法！没有 NP 完全性理论，研究人员将浪费时间追随没有前途的研究方向。

其他下界。

• 信息论的。 在第 X.Y 节中，我们看到插入最多使用 N² 次比较来对 N 个项目进行排序，而归并排序最多使用 N log N 次比较。一个自然的问题是我们是否可以做得更好，也许最多使用 5N 次比较，甚至 1/2 N log N 次比较。为了使问题更加明确，我们必须明确陈述我们的计算模型（决策树）。在这里，我们假设我们只通过 less() 函数访问数据。由 X 提出的一个引人注目的定理表明，没有（基于比较的）排序算法可以保证在少于 ~ N log N 次比较中对 N 个不同元素的每个输入进行排序。要理解原因，观察到每次比较（调用 less）提供一位信息。为了识别正确的排列，您需要 log N! 位信息，而 log N! ~ N log N。这告诉我们，归并排序是（渐近地）最佳的排序算法。不存在任何排序算法（甚至是尚未想象的算法）会使用更少的比较。
  
• 3-Sum 困难。 给定一组 N 个整数，其中任意三个数相加是否等于 0？存在二次算法（参见练习 xyz），但没有已知的次二次算法。3-SUM 线性归约到计算几何中的许多问题。（查找平面上的点集是否有 3 个共线，决定平面上的线段集是否可以被一条线分成两个子集，确定一组三角形是否覆盖单位正方形，您是否可以将多边形 P 移动到完全位于另一个多边形 Q 内部，机器人运动规划）。
  

蛮力 TSP 需要 N! 步。使用动态规划，可以将其减少到 2^N。最佳下界 = N。计算复杂性的本质 = 尝试找到匹配的上界和下界。

电路复杂性。

还有其他定义和衡量计算复杂性的方法。具有 n 个输入的布尔电路可以计算 n 个变量的任何布尔函数。我们可以将电路输出 1 的大小为 n 的二进制字符串集合与语言中的字符串集合相关联。我们需要一个用于每个输入大小 n 的电路。Shannon（1949）提出了电路大小作为复杂性的度量。已知，如果语言在 P 中，则语言具有均匀多项式电路。

物理和模拟计算。

P = NP 问题是关于图灵机和经典数字计算机能力的数学问题。我们也可以思考模拟计算机是否也是如此。模拟 意味着任何“确定性物理设备，使用固定数量的物理变量来表示每个问题变量。” 内部状态由连续变量而非离散变量表示。例如，肥皂泡沫，蛋白质折叠，量子计算，齿轮，时间旅行，黑洞等。

Vergis, Steiglitz, and Dickinson 提出了强克尔图灵论文的模拟形式：

任何有限的模拟计算机都可以被数字计算机高效模拟，即数字计算机模拟模拟计算机所需的时间受限于模拟计算机使用的资源的多项式函数。

模拟计算机的资源可以是时间、体积、质量、能量、扭矩或角动量。参考：模拟计算的物理学

任何合理的计算模型（例如，不涉及指数并行性）都可以通过图灵机（辅以硬件随机数生成器）在多项式时间内模拟。

参考：斯科特·阿伦森。可以为物理学提供新的见解。有一天，“NP 完全问题的被假定为难以解决可能被视为寻找新物理理论的有用约束”，就像热力学第二定律一样。仍然可以通过实验证伪，但不要浪费时间…

• 肥皂泡。 传说你可以解决斯坦纳树问题。实际上，只能找到一个局部最小值，并且可能需要一段时间才能找到。
  
• 量子计算。 一种推测性的计算模型 - 量子计算机 - 可能能够在确定性图灵机无法做到的多项式时间内解决一些问题。彼得·肖尔发现了一个用于分解 N 位整数的 N³ 算法，但在经典计算机上已知的最佳算法需要指数时间。同样的想法可能导致在模拟量子力学系统时获得可比较的加速。这解释了量子计算引起的最近激动，因为它可能导致计算的范式转变。然而，量子计算机尚未违反扩展的丘奇-图灵论题，因为我们尚不知道如何构建它们。（难以利用，因为许多量子信息似乎很容易被与外界的相互作用所破坏，即退相干。）此外，仍然有可能有人在经典计算机上发现一个多项式时间算法来分解，尽管大多数专家认为这是不可能的。格罗弗的算法：在 sqrt(N)时间内搜索而不是 N。
  理查德·费曼在 1982 年表明，经典计算机无法模拟量子力学系统而不会指数级减速（争论的关键在于图灵机具有局部性，而量子力学包括“利用远距作用”）。量子计算机可能能够解决这个问题。费曼关于建造一个模拟物理的计算机的引用…

“我想要的模拟规则是，用于模拟大型物理系统所需的计算机元素数量仅与物理系统的时空体积成正比。我不想出现爆炸。”

• 用“受限于”替换“与…成正比”来重新表述现代复杂性理论。
  德乔萨提出的算法在量子计算机上的运行速度被证明比确定性图灵机快得多。（尽管如果图灵机可以访问硬件随机数生成器并且可以以可忽略的概率出错，指数差距就不存在。量子计算机可以生成真正的随机性。）

素数和合数。

通过提供一个因子很容易说服某人一个数字是合数。然后，这个人只需通过长除法检查你是否对他们撒谎。马林·梅森猜想形如 2^p - 1 的数字对于 p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 和 257 是素数。他对 p = 67 的猜想在两百五十多年后的 1903 年被 F·N·科尔推翻。根据 E·T·贝尔的书籍数学：科学的女王和仆人

在 AMS 的十月会议上，Cole 宣布了一个关于“大数的因式分解”的讲座。他默不作声地走到黑板前，手算出了 2⁶⁷ 的值，仔细地减去 1。然后他将两个数相乘（分别是 193707721 和 761838257287）。黑板上写下的两个结果是相等的。Cole 默默地走回座位，据说这是 AMS 会议中唯一一次观众鼓掌的讲座。没有问题。根据他所说，Cole 花了大约 3 年的每个星期日来找到这个因式分解。

记录上 2⁶⁷ - 1 = 193707721 × 761838257287 = 147573952589676412927。

Q + A

Q. 多项式算法总是有用吗？

A. 不，需要 N¹⁰⁰ 或 10¹⁰⁰ N² 步的算法在实践中与指数算法一样无用。实践中产生的常数通常足够小，使得多项式时间算法适用于巨大问题，因此多项式性通常作为实践中有用的替代品。

Q. 为什么所有搜索问题的类别被命名为 NP？

A. NP 的最初定义是基于非确定性图灵机的：NP 是所有可以在非确定性图灵机上多项式时间内解决的决策问题的集合。粗略地说，确定性和非确定性图灵机之间的区别在于前者像传统计算机一样运行，按顺序执行每个指令，形成一个计算路径；非确定性图灵机可以“分支”，其中每个分支可以并行执行不同的语句，形成一个计算树（如果树中的任何路径导致 YES，则我们接受；如果所有路径导致 NO，则我们拒绝。）这就是 NP 中的 N 来源。事实证明这两个定义是等价的，但现在更广泛使用证书的定义。（此外，Karp 的 1972 年论文使用了多项式时间可验证性的定义。）

Q. 复杂度类 NP-难是什么？

A. 几个竞争性定义。我们定义一个问题（决策、搜索或优化）问题为 NP-难，如果在多项式时间内解决它将意味着 P = NP。定义隐含地使用图灵归约（扩展到搜索问题）。

Q. 在多项式时间内对整数 N 因式分解有什么困难之处 - 我不能只将小于 N（或 √N）的所有潜在因子分成 x 并查看是否有余数为零吗？

A. 算法是正确的，但请记住只需 lg N 位来表示整数 N。因此，为了使算法在输入大小上是多项式的，它必须在 lg N 中是多项式的，而不是 N。

Q. 检查一个整数是否为合数可以在多项式时间内解决，但找到它的因子却未知（或被认为）不可解吗？

A. 有方法证明一个数是合数而不需要得到它的任何因子。数论中的一个著名定理（费马小定理）暗示，如果你有两个整数 a 和 p，使得（i）a 不是 p 的倍数且（ii）a^(p-1) != 1 (mod p)，那么 p 不是质数。

Q. 是否存在一个在量子计算机上多项式可解的决策问题，但可以证明不在 P 中？

A. 这是一个未解决的研究问题。FACTOR 是一个候选项，但没有证据表明 FACTOR 不在 P 中，尽管普遍认为它不在 P 中。

Q. NP = EXPTIME 吗？

A. 专家们认为不是，但他们无法证明。

Q. 假设有人证明 P = NP。这将有什么实际后果？

A. 这取决于问题是如何解决的。显然，如果证明 P = NP，那将是一个显著的理论突破。在实践中，如果 P = NP 的证明为一个重要的 NP 完全问题建立了一个快速算法，那可能具有重大意义。如果证明导致旅行商问题的一个 2¹⁰⁰ N¹¹⁷ 的算法（且常数和指数无法减少），那将没有太大的实际影响。也可能有人通过间接手段证明 P = NP，从而根本没有算法！

Q. 假设有人证明 P != NP。这将会有什么实际后果？

A. 这将是一个显著的理论突破，并巩固了计算复杂性的许多基础。

Q. 假设 P = NP。这是否意味着确定性图灵机与非确定性图灵机相同？

A. 不完全是这样。例如，即使 P = NP，非确定性图灵机可能能够在与最佳确定性图灵机相比为 N³ 的时间内解决问题。如果 P = NP，这只是意味着这两种类型的机器在多项式时间内解决相同的决策问题，但它并不说明多项式的次数。

Q. 我在哪里可以了解更多关于 NP 完全性的知识？

A. 权威参考仍然是 Garey 和 Johnson 的《计算机与难解性：NP 完全性理论指南》。许多最重要的后续发现都记录在 David Johnson 的NP 完全性专栏中。

练习

1. 假设 X 是 NP 完全的，X 多项式时间归约到 Y，Y 多项式时间归约到 X。那么 Y 是否一定是 NP 完全的？
   答案：不是，因为 Y 可能不在 NP 中。例如，如果 X = CIRCUIT-SAT，Y = CO-CIRCUIT-SAT，那么 X 和 Y 满足条件，但未知 Y 是否在 NP 中。请注意，答案取决于我们对多项式时间归约的定义（应为图灵归约而不是 Karp 归约）。
   

• 解释为什么顶点覆盖问题的优化版本不一定是一个搜索问题。答案：目前似乎没有有效的方法来证明一个所谓的解决方案是最佳的（即使我们可以在问题的搜索版本上使用二分搜索来找到最佳解决方案）。网络练习

1. 子集和。 给定 N 个正整数和一个目标值 V，确定是否存在一个子集，其和恰好为 V。将整数分成 4 个相等的组。通过蛮力法列举和存储每组中的所有子集和。让 A、B、C 和 D 分别表示四个组的子集和。目标是找到整数 a、b、c 和 d，使得 a + b + c + d = V，其中 a 在 A 中，b 在 B 中，c 在 C 中，d 在 D 中。现在，使用一个堆来列举 a 在 A 中，b 在 B 中的和。同时，使用另一个堆以递减顺序列举 c 在 C 中，d 在 D 中的和。
   
2. 平方根之和。 两个整数平方根之和之间的最小非零差是多少？给定 n 和 k，找到

| √a1 + √a2 + ... + √ak - √b1 - √b2 - ... - √bk |

1. 其中 ai 和 bi 在 0 和 n 之间。例如 r(20, 2) = √10 + √11 - √5 - √18 和 r(20, 3) = √5 + √6 + √18 - √4 - √12 - √12。提示：列举前 n/2 个整数的平方根之和的 2^(n/2) 种可能，并将该集合命名为 A，列举后 n/2 个整数的平方根之和的 2^(n/2) 种可能，并将其命名为 B。现在按排序顺序列举 a 在 A 中，b 在 B 中的和，其中 a 在 A 中，b 在 B 中。寻找差异非常微小的和。
2. 划分钻石。 给定 N（大约 36）类 D 钻石，将它们分成两组，使它们的总重量尽可能接近。假设重量是实数（以克拉为单位）。
   
3. DAG 中的哈密顿路径。 给定一个有向无环图 G，给出一个 O(n+m) 时间复杂度的算法来测试它是否是哈密顿图。提示：拓扑排序。
   
4. 如果假设 P 不等于 NP，从旅行推销员问题是 NP 完全的这一事实中我们可以推断出以下哪些？

1. 不存在一个能解决 TSP 问题的任意实例的算法。
   
2. 不存在一个能高效解决 TSP 任意实例的算法。
   
3. 存在一个高效解决任意 TSP 实例的算法，但没有人能找到它。
   
4. TSP 不在 P 中。
   
5. 所有保证解决 TSP 的算法对于某些输入点族都在多项式时间内运行。
   
6. 所有保证解决 TSP 的算法对于所有输入点族都运行在指数时间内。
   

5. 答案：(b) 和 (d)。
   
6. 如果假设 P 不等于 NP，从 PRIMALITY 在 NP 中但不知道是否 NP 完全这一事实中我们可以推断出以下哪些？

1. 存在一个能解决任意 PRIMALITY 实例的算法。
   
2. 存在一个能高效解决任意 PRIMALITY 实例的算法。
   
3. 如果我们找到 PRIMALITY 的一个高效算法，我们可以立即将其用作黑盒来解决 TSP。
   

7. 答案：我们只能推断 (a)，因为所有 P 中的问题都是可判定的。如果 P != NP，那么有些 NP 中的问题既不在 P 中也不是 NP 完全的。PRIMALITY 可能是其中之一（尽管最近已被证明不是）。部分 © 不能被推断，因为我们不知道 PRIMALITY 是否是 NP 完全的。
   
8. 以下哪些是 NP 完全的？

1. 蛮力 TSP 算法。
   
2. 用于排序的快速排序算法。
   
3. 停机问题。
   
4. 希尔伯特的第十个问题。
   

9. 答案：无。NP 完全性涉及问题而不是问题的具体算法。停机问题和希尔伯特的第十个问题是不可判定的，因此它们不在 NP 中（所有 NP 完全问题都在 NP 中）。
   
10. 假设 X 和 Y 是两个决策问题。假设我们知道 X 可归约到 Y。我们可以推断以下哪些？

1. 如果 Y 是 NP 完全的，则 X 也是。
   
2. 如果 X 是 NP 完全的，那么 Y 也是。
   
3. 如果 Y 是 NP 完全的且 X 在 NP 中，则 X 是 NP 完全的。
   
4. 如果 X 是 NP 完全的且 Y 在 NP 中，则 Y 是 NP 完全的。
   
5. X 和 Y 不能同时是 NP 完全的。
   
6. 如果 X 在 P 中，那么 Y 也在 P 中。
   
7. 如果 Y 在 P 中，那么 X 也在 P 中。
   

11. 答案：(d) 和 (g)。X 可归约到 Y 意味着如果你有一个能高效解决 Y 的黑盒，你可以用它来高效解决 X。X 不比 Y 更难。
    
12. 证明 CIRCUIT-SAT 可归约到 CIRCUIT-DIFF。提示：创建一个具有 N 个输入的电路，总是输出 0。
    
13. 证明 CIRCUIT-DIFF 可归约到 CIRCUIT-SAT。
    
14. 证明 DETERMINANT 在 NP 中：给定一个 N×N 的整数矩阵 A，det(A) = 0 吗？
    解法：证书是一个非零向量 x，使得 Ax = 0。
    
15. 证明 FULL-RANK 在 NP 中：给定一个 N×N 的整数矩阵 A，det(A) ≠ 0 吗？
    解法：证书是一个 N×N 的逆矩阵 B，使得 AB = I。
    
16. 搜索问题 vs. 决策问题。 我们可以使用相应的决策问题来制定一个搜索问题。例如，找到整数 N 的素因子分解问题可以使用决策问题来制定：给定两个整数 N 和 L，N 是否有一个严格小于 L 的非平凡因子。如果相应的决策问题可在多项式时间内解决，那么搜索问题也可以。为了理解原因，我们可以通过使用不同的 L 值和二分查找来高效地找到 N 的最小因子 p。一旦我们有了因子 p，我们可以对 N/p 重复这个过程。
    通常我们可以证明搜索问题和决策问题在运行时间上等价于多项式因子。Papadimitriou（示例 10.8）给出了一个有趣的反例。给定 N 个正整数，它们的和小于 2^N - 1，找到两个和相等的子集。例如，下面的 10 个数字的和为 1014 < 1023。

23 47 59 88 91 100 111 133 157 205

1. 由于 N 个整数的子集（2^N）比 1 到 1014 之间的数字更多，必然存在两个不同的子集具有相同的和。但没有人知道一个多项式时间算法来 找到 这样的子集。另一方面，自然的决策问题在常数时间内是易解的：是否存在两个和相同的数字子集？
2. 普拉特素性证书。 证明 PRIMES 属于 NP。使用莱默定理（费马小定理的逆定理），它断言大于 1 的整数 p 是素数当且仅当存在一个整数 x，使得 x^(N-1) = 1 (mod p) 且 x^((p-1)/d) ≠ 1 (mod p) 对于 p-1 的所有素数因子 d 都成立。例如，如果 N = 7919，那么 p-1 的素因子分解为 7918 = 2 × 37 × 107。现在 x = 7 满足 7⁷⁹¹⁸ = 1 (mod 7919)，但 7^(7918/2) ≠ 1 (mod 7919)，7^(7918/37) ≠ 1 (mod 7919)，7^(7918/107) ≠ 1 (mod 7919)。这证明了 7919 是素数（假设你递归地证明了 2、37 和 107 是素数）。
   
3. 佩尔方程。 找到佩尔方程 x² - 92y² = 1 的所有正整数解。解答：(1151, 120), (2649601, 276240)，等等。有无穷多解，但每个连续的���大约是前一个解的 2300 倍。
   
4. 佩尔方程。 在 1657 年，皮埃尔·费马向他的同事们提出了以下问题：给定一个正整数 c，找到一个正整数 y，使得 cy² 是一个完全平方数。费马使用了 c = 109。结果表明最小解为 (x, y) = (158,070,671,986,249, 15,140,424,455,100)。编写一个程序 Pell.java，读入一个整数 c，并找到佩尔方程的最小解：x² - c y² = 1。尝试 c = 61。最小解为 (1,766,319,049, 226,153,980)。对于 c = 313，最小解为 ( 3,218,812,082,913,484,91,819,380,158,564,160)。该问题在多项式步数内是无法解决的（作为输入 c 位数的函数），因为输出可能需要指数级的位数！
   
5. 3-COLOR 归约到 4-COLOR。 证明 3-COLOR 多项式归约到 4-COLOR。提示：给定一个 3-COLOR 实例 G，通过向 G 添加一个特殊顶点 x 并将其连接到 G 中的所有顶点，创建一个 4-COLOR 实例 G’。
   
6. 3-SAT 是自可归约的。 证明 3-SAT 是自可归约的。也就是说，给定一个回答任意 3-SAT 公式是否可满足的预言机，设计一个算法可以找到一个满足条件的 3-SAT 公式（假设它是可满足的）。你的算法应在多项式时间内运行，再加上多项式次调用预言机。
   
7. 3-COLOR 是自可归约的。 证明 3-COLOR 是自可归约的。也就是说，给定一个回答任意图 G 是否可 3-染色的预言机，设计一个算法可以对图进行 3-染色（假设它是可 3-染色的）。你的算法应在多项式时间内运行，再加上多项式次调用预言机。