普林斯顿算法讲义（四）（2）https://developer.aliyun.com/article/1484180
- AMPL 是数学规划的建模语言。文件 beer.mod 和 beer.dat 指定了酿酒厂问题的模型和数据。
[wayne:tombstone] ~> ampl ILOG AMPL 9.100 AMPL Version 20021038 (SunOS 5.8) ampl: model beer.mod; ampl: data beer.dat; ampl: solve; ILOG CPLEX 9.100 CPLEX 9.1.0: optimal solution; objective 800 2 dual simplex iterations (1 in phase I) ampl: display x; x [*] := ale 12 beer 28 ; ampl: display constraints.dual; x [*] := corn 1 hops 2 malt 0 ;
- Microsoft Excel 在 Windows 上有一个基本的求解器插件，但在 Mac 上不再可用。
问答
Q. 无向最短路径与带负权重的有向最短路径？
A. 需要更聪明的简化来避免负循环（通过非二部匹配）。
练习
- 最大公约数和最小公倍数. 将最小公倍数简化为最大公约数。
- 表 k-和. 给定一个 k 行 N 列的整数表，是否有 k 个数相加为 0，每个数来自 k 行中的一个？
- 硬币不同。 给定 N 枚硬币和一个天平，确定这些硬币是否都有不同的重量。证明解决该问题的任何算法的复杂度至少为 N log N。提示：你可以使用这样一个事实，即给定 N 个实数，元素的不同性在线性决策树模型中至少需要 N log N 次比较（在这个模型中，你可以对 N 个元素的任意线性组合进行比较，例如，x1 + 2x2 < x3）。
- 集合相等。 给定两个集合 S 和 T，S 是否等于 T？给出一个 O(N log N)的算法和一个匹配的下界。
- 集合子集。 给定两个集合 S 和 T，S 是否是 T 的子集？给出一个 O(N log N)的算法和一个匹配的下界。
- 集合不相交。 给定两个集合 S 和 T，S 与 T 的交集是否为空集？给出一个 O(N log N)的算法和一个匹配的下界。（由于 S 和 T 是集合，因此两者中没有重复元素。）
解决方案。 要获得 O(N log N)的上界，对 S 和 T 中的元素的并集进行排序，并检查重复项。 - 集合不相交。 给定两个按升序排列的集合 S 和 T，S 与 T 的交集是否为空集？证明一个 Omega(N log N)的下界或给出一个 O(N)的算法。
- 合并两个列表的下界。 展示任何基于比较的合并两个大小为 N 的列表的算法在最坏情况下至少需要 2N-1 次比较。解决方案：即使所有元素都不同，下界也成立。如果第 i 个和第(i+1)个最小的元素在不同的列表中，则它们必须进行比较。
- 二分查找的下界。 需要 log(N+1)次比较。解决方案：即使所有元素都不同，下界也成立……
- 欧几里得 TSP 和 MST 下界。 对于欧几里得 TSP 或欧几里得 MST，给出一个 Omega(N log N)的下界（需要代数决策树来理解，因为你希望允许一个合理的算法来计算距离）。解决方案：在一条线上选择 N 个点。最优路径必须按升序访问这些点。
- 模式的下界。 模式的 Theta(N log N)下界。解决方案：可以通过找到模式并检查是否超过一个来解决元素不同性问题。
- 最接近对的下界。 最接近对的 Theta(N log N)下界。解决方案：如果有一个次线性对数算法，可以通过找到最接近对并检查它们是否相等来在次线性对数时间内解决元素不同性问题。
- 最小和次小元素。 描述如何使用最多 N + log N 次比较找到最小和次小元素。解决方案：将元素分成一对一对，并比较每对中的两个元素。使用每对中的 N/2 个获胜者进行递归。经过 N-1 次比较后，我们得到最小元素。请注意，每个元素最多与 log N 个其他元素进行比较。特别是，最小元素最多与 log N 个其他元素进行比较，其中一个必须是次小元素。如果你跟踪所有的比较，你可以记住涉及最小元素的 log N 次比较，并进行比较。
- 计数逆序对。 证明 Theta(N log N)的下界。这是一个尚未解决的研究问题。
- 螺母和螺栓。 证明快速排序部分的螺母和螺栓问题的 Theta(N log N)下界。[已知匹配的最坏情况上界为 O(N log N)，但这是非常复杂的。]
- 存在符号表。 假设你有一个支持插入和存在操作的基于比较的算法，每次操作都只需要 O(1)次比较。解释为什么在这种计算模型中这是不可能的。解决方案：为了在 O(N)时间内解决元素不同性问题，对于每个 N 个元素，检查它是否已经在数据结构中（如果是，则这是一个重复项）；如果不是，则插入它。
- 使用整数规划模型一个形如 x ≤ y 的约束（Ax = b，x >= 0，x 为整数）。
- 使用整数规划模型一个形如 x = {0 或 1}的约束。
- 使用整数规划模型一个形如 x = {1 或 2 或 4}的约束。
- Tait 着色。 使用 IP 模拟 3 边着色立方图。
- 为患者分配器官捐赠者。
- 二部顶点覆盖。 减少到最大流。
- 传递闭包和传递闭包。 将传递闭包减少到传递闭包，反之亦然（当运行时间仅作为顶点数 V 的函数时）。也可减少到布尔矩阵乘法。
- 3SUM’。 给定三组整数 A、B 和 C，总大小为 n，是否存在 A 中的 a，B 中的 b 和 C 中的 c，使得 a + b = c？证明 3SUM 线性时间减少到 3SUM’，反之亦然。
解决方案。 要显示 3SUM 减少到 3SUM’，设置 A = S，B = S，C = -S。
要显示 3SUM’减少到 3SUM，假设所有整数都是正数（如果不是，则将 k 添加到 A 和 B 中的每个元素，将 2K 添加到 C 中的每个元素）。设置 m = 2 max(A, B, C)。对于 A 中的每个元素 a，在 S 中放置 a + m。对于 B 中的每个元素 b，在 S 中放置 b。对于 C 中的每个元素，在 S 中放置-c -m。 - 不等式满足等式。 给定线性不等式系统A x ≤ b，设计一个线性规划来确定在任何可行解x中哪些不等式必须满足等式。
- 等式约束。 使用两个<=约束模拟线性规划等式约束。
- 无限制变量。 使用两个非负变量 y 和 z 来模拟线性规划无限制变量 x。
- 无界 LP。 如果（P）是无界的，则存在一个矢量 d >= 0，使得 Ad <= 0 且 cd > 0。首先解释为什么如果存在这样的矢量 d，则问题是无界的。接下来，修改单纯形算法，在 LP 无界时报告这样的矢量。答案：根据假设 b >= 0 且 x = 0 是可行的。因此，对于任何正常数α，αd 都是可行的，并且具有目标值αcd。通过检查最小比率规则是否失败，可以识别矢量 d。在这种情况下，列 q 中的条目为非正（Ad <= 0），并且目标函数系数为正（cd > 0）。
- 减少成本。 修改单纯形算法以报告减少的成本（影子价格）。给出经济解释。
- 丹齐格的最陡边规则。 修改单纯形算法，使其始终选择最正的目标函数系数。
- 循环。 给出一个导致单纯形算法（使用最陡边规则）循环的病态线性规划输入。
- 瓶颈分配问题。 给定 N 个男人和 N 个女人。每个人有 M 个属性。每个人指定异性的一组理想属性。找到一个完美匹配，其中最不幸的人与指定属性最少的伴侣匹配。将此问题减少到分配问题。
解决方案。 创建一个边权重图，其中边的权重是两个人中满足的可取属性的最小数量。目标是最大化分配中最小权重边的权重。解决此问题的一种方法是使用二分查找（消除所有权重小于给定阈值的边）并解决结果的二部完美匹配问题。 - 中国邮递员问题。 给定一个强连通的有向图 G，找到一个最短长度的有向循环，该循环至少经过每条边一次。（事实证明，最佳循环将最多访问每条边两次。）如果每个顶点都是平衡的，则图是欧拉图：其度等于其出度。将不平衡的顶点分为两组：L = 出度小于入度的顶点，R = 出度大于入度的顶点。通过在 L 中的一个顶点到 R 中的一个顶点添加一个有向路径，我们改善了平衡性。在 (L, R) 上形成一个加权二部图，其中从 v 到 w 的边的权重是 G 中从 v 到 w 的最短路径的长度。找到一个最小权重匹配，并将这些边添加到 G 中使其成为欧拉图。然后，找到一个循环。这被称为 Edmonds-Johnson（1973）算法。（类似的算法适用于无向图，但需要在非二部图中找到一个最小权重完美匹配。）
6.6 难解性
原文：
algs4.cs.princeton.edu/66intractability译者：飞龙
本节正在建设中。复杂性理论的目标是理解高效计算的本质。我们已经学习了算法分析，这使我们能够根据它们消耗的资源量对算法进行分类。在本节中，我们将学习一个丰富的问题类别，至今还没有人能够设计出高效的算法。
计算复杂性。
随着数字计算机在 1940 年代和 1950 年代的发展，图灵机成为计算的理论模型。在 1960 年代，Hartmanis 和 Stearns 提出了将计算机所需的时间和内存作为输入大小的函数来衡量。他们以图灵机为基础定义了复杂性类，并证明了一些问题具有“无法通过巧妙编程规避的固有复杂性”。他们还证明了直观观念的一个正式版本（时间层次定理），即如果给予更多时间或空间，图灵机可以计算更多事物。换句话说，无论问题有多难（时间和空间要求），总会有更难的问题。
计算复杂性是确定不同问题的资源需求的艺术和科学。计算复杂性涉及对任何可能的问题算法的断言。做出这样的断言比理解问题的一个特定算法的运行时间要困难得多，因为我们必须推理所有可能的算法（甚至是尚未发现的算法）。这使得计算复杂性成为一个令人兴奋但又令人望而生畏的研究领域。我们将概述一些其最重要的思想和实际产物。
多项式时间。
我们已经分析了算法的运行时间作为其输入大小的函数。在解决给定问题时，我们更喜欢一个需要 8 N log N 步的算法，而不是需要 3 N² 步的算法，因为当 N 很大时，第一个算法比第二个算法快得多。第二个算法最终会解决相同的问题（但可能需要几小时而不是几秒）。相比之下，指数时间算法具有不同的定性行为。例如，对于 TSP 的暴力算法可能需要 N! 步。即使宇宙中的每个电子（10⁷⁹）都具有今天最快超级计算机（每秒 10¹² 条指令）的能力，并且每个电子在解决问题上工作了宇宙寿命（10¹⁷ 秒），也几乎无法解决 N = 1,000 的问题，因为 1000! >> 10¹⁰⁰⁰ >> 10⁷⁹ * 10¹² * 10¹⁷。指数增长使技术变革相形见绌。我们将任何运行时间受输入大小多项式限制的算法（例如 N log N 或 N²）称为多项式时间算法。如果问题没有多项式时间算法，则称该问题为难解问题。
创建 N、N³、N⁵、N¹⁰、1.1N、2N、N! 的对数对数比例图，如 Harel 第 74 页所示。
随着程序员对计算的经验增加，人们逐渐意识到多项式时间算法是有用的，而指数时间算法则不是。在一篇非常有影响力的论文中，Jack Edmonds 将多项式算法称为“好算法”，并认为多项式时间是高效计算的一个很好的替代。Kurt Godel 在 1956 年给 von Neumann 写了一封信（第 9 页），其中包含了多项式性是一个可取特征的（隐含）概念。早在 1953 年，von Neumann 就认���到了多项式和指数算法之间的定性差异。根据多项式和指数时间对问题进行分类的想法深刻地改变了人们对计算问题的看法。
NP。
非正式地，我们将搜索问题定义为一个计算问题，我们在（可能巨大的）可能性中寻找解决方案，但是当我们找到解决方案时，我们可以轻松检查它是否解决了我们的问题。给定搜索问题的一个实例 I（指定问题的一些输入数据），我们的目标是找到一个解决方案 S（符合某些预先指定标准的实体）或报告不存在这样的解决方案。为了成为搜索问题，我们要求很容易检查 S 是否确实是一个解决方案。在这里，我们指的是在输入 I 的大小上是多项式时间。复杂性类NP是所有搜索问题的集合。以下是一些例子。
- *线性方程组。*给定线性方程系统 Ax = b，找到满足方程的解 x（如果存在）。这个问题属于 NP，因为如果我们得到一个所谓的解 x，我们可以通过将 x 代入并验证每个方程来检查 Ax = b。
- *线性规划。*给定线性不等式系统 Ax ≤ b，找到满足不等式的解 x（如果存在）。这个问题属于 NP，因为如果我们得到一个所谓的解 x，我们可以通过将 x 代入并验证每个不等式来检查 Ax ≤ b。
- *整数线性规划。*给定线性不等式系统 Ax ≤ b，找到满足不等式的二进制（0/1）解 x（如果存在）。这个问题属于 NP，因为如果我们得到一个所谓的解 x，我们可以通过将 x 代入并验证每个不等式来检查 Ax ≤ b。
虽然检查对这三个问题的提议解决方案很容易，但是从头开始找到解决方案有多困难？
备注：我们对 NP 的定义略有不同。在历史上，复杂性类别是根据决策问题（是-否问题）来定义的。例如，给定矩阵A和向量b，是否存在解x使得Ax = b？
P。
复杂性类 P 是所有可以在多项式时间内解决的搜索问题的集合（在确定性图灵机上）。与以前一样，我们根据搜索问题（而不是决策问题）来定义 P。它涵盖了我们可以在实际机器上解决的大多数问题。以下列出了一些例子：
| 问题 | 描述 | 算法 | 实例 | 解决方案 |
| GCD | 找到两个整数 x 和 y 的最大公约数。 | 欧几里得算法（欧几里得，公元前 300 年） | 34, 51 | 17 |
| STCONN | 给定图 G 和两个顶点 s 和 t，找到从 s 到 t 的路径。 | BFS 或 DFS（Theseus） | ||
| SORT | 找到将元素按升序排列的排列。 | 归并排序（冯·诺伊曼，1945） | 2.3 8.5 1.2 9.1 2.2 0.3 | 5 2 4 0 1 3 |
| PLANARITY | 给定一个图 G，在平面上画出它，使得没有两条边相交。 | （Hopcroft-Tarjan, 1974） | ||
| LSOLVE | 给定矩阵 A 和向量 b，找到一个向量 x 使得 Ax = b。 | 高斯消元（Edmonds, 1967） | x+y=1 2x+4y=3 | x = 1/2 y = 1/2 |
| LP | 给定矩阵 A 和向量 b，找到一个向量 x 使得 Ax ≤ b？ | 椭球算法（Khachiyan, 1979） | x+y≤1 2x+4y≤3 | x = 0 y = 0 |
| DIOPHANTINE | 给定一个具有整数系数的（稀疏）一元多项式，找到一个整数根？ | （Smale 等，1999） | x⁵ - 32 | x = 2 |
扩展的丘奇-图灵论断。
在 1960 年代中期，Cobham 和 Edmonds 独立观察到，在一个广泛的计算模型范围内，可以在多项式步骤内解决的问题集保持不变，从确定性图灵机到 RAM 机。扩展的丘奇-图灵论题断言图灵机与任何物理计算设备一样高效。也就是说，P 是在这个宇宙中可以在多项式时间内解决的搜索问题的集合。如果某个硬件解决了大小为 N 的问题，时间为 T(N)，扩展的丘奇-图灵论题断言确定���图灵机可以在时间 T(N)^k 内解决它，其中 k 是某个固定常数，k 取决于特定问题。Andy Yao 表达了这个论题的广泛含义：
它们暗示，至少从原理上讲，要使未来的计算机更加高效，只需要专注于改进现代计算机设计的实现技术。
换句话说，任何合理的计算模型都可以在（概率性）图灵机上高效模拟。对于所有已知的物理通用计算机，扩展的丘奇-图灵论题都是成立的。对于随机访问机器（例如您的 PC 或 Mac），常数 k = 2。因此，例如，如果随机访问机器可以在时间 N^(3/2)内执行计算，则图灵机可以在时间 N³内执行相同的计算。
P = NP 吗？
我们这个时代最深刻的科学问题之一是P = NP。也就是说，所有搜索问题是否都能在多项式时间内解决？Clay Foundation 为解决这个问题提供了100 万美元的千禧奖。以下是一些关于何时解决这个问题的猜测。压倒性的共识是 P != NP，但没有人能够证明。
视频中荷马·辛普森对 P = NP 进行演讲，伴随着《失乐园》的音乐。
哥德尔写给冯·诺伊曼的信预见了 P = NP 问题。他意识到如果 P = NP（可满足性在 P 中），那么“将会有最重要的后果”，因为那时“数学家关于是或否问题的思维工作可以完全被机器取代”。他询问哪些组合问题存在更有效的替代方案以避免穷举搜索。
NP 完全性。
非正式地说，NP 完全问题是 NP 中“最难”的问题；它们最有可能不在 P 中。定义：如果（i）它在 NP 中且（ii）每个 NP 问题都可以多项式归约到它，则问题是NP 完全的。定义 NP 完全性的概念并不意味着这样的问题存在。事实上，NP 完全问题的存在是一件令人惊奇的事情。我们无法通过从每个 NP 问题进行归约来证明问题是 NP 完全的，因为它们有无限多个。在 1960 年代，Cook 和 Levin 证明了 SAT 是 NP 完全的。
这是普遍性的一个例子：如果我们可以解决任何 NP 完全问题，那么我们就可以解决 NP 中的任何问题。独特的科学发现为所有类型的问题提供了共同的解释。更令人惊讶的是，存在着“自然”的 NP 完全问题。
NP 完全性对自然科学的影响是不可否认的。一旦发现了第一个 NP 完全问题，难以解决性质就像“冲击波一样在问题空间中蔓延”，首先是在计算机科学中，然后传播到其他科学学科。帕帕迪米特里奥列出了 20 个不同的科学学科，它们正在应对内部问题。最终，科学家们在意识到他们的核心问题是 NP 完全问题后，发现了它们固有的复杂性。每年有 6000 篇科学论文中提到 NP 完全性作为一个关键词。它“涵盖了计算、科学、数学努力的广泛领域，并似乎粗略地界定了数学家和科学家一直渴望可行计算的范围。”[帕帕迪米特里奥]很少有科学理论有如此广泛和深远的影响。
一些 NP 完全问题。 自从发现 SAT 是 NP 完全以来，已经确定了成千上万个问题是 NP 完全的。1972 年，卡普尔表明离散数学中最臭名昭著的 21 个问题是NP 完全的，包括Tsp，Knapsack，3Color和Clique。科学家未能为这 21 个问题找到有效算法，尽管他们不知道这些问题是 NP 完全的，这是最早表明 P != NP 的证据之一。下面列出了一些 NP 完全问题的样本。这里还有一些NP 完全问题。这只是为了说明它们的多样性和普遍性。
- Bin Packing. 你有 n 个物品和 m 个箱子。第 i 个物品重 w[i]磅。每个箱子最多可以容纳 W 磅。你能否将所有 n 个物品装入 m 个箱子中，而不违反给定的重量限制？
这个问题有许多工业应用。例如，UPS 可能需要从一个配送中心将大量包裹（物品）运送到另一个中心。它希望将它们放入卡车（箱子）中，并尽可能少地使用卡车。其他 NP 完全变体允许体积要求：每个三维包裹占用空间，你还必须担心如何在卡车内安排包裹。 - Knapsack. 你有一组 n 个物品。第 i 个物品重 w[i]磅，具有利益 b[i]。你能否选择一些物品的子集，使得总重量小于或等于 W，总利益大于或等于 B？例如，当你去露营时，你必须根据它们的重量和效用选择要带的物品。或者，假设你正在入室行窃，只能在你的背包中携带 W 磅的赃物。每个物品 i 重 w[i]磅，有 b[i]美元的市场价值。你应该偷哪些物品？
- Subset Sum. 给定 n 个整数，是否存在一个子集，其和恰好为 B？例如，假设这些整数是{4, 5, 8, 13, 15, 24, 33}。如果 B = 36，则答案是 yes（且 4, 8, 24 是一个证明）。如果 B = 14，则答案是 no。
- Partition. 给定 n 个整数，你能将它们分成两个子集，使得每个子集的和相等吗？例如，假设这些整数是{4, 5, 8, 13, 15, 24, 33}。那么答案是
yes，{5, 13, 33}是一个证明。双处理器的负载平衡。 - 整数线性规划. 给定一个整数矩阵 A 和一个整数向量 b，是否存在一个整数向量 x 使得 Ax ≤ b？这是运筹学中的一个核心问题，因为许多优化问题可以用这种方式表达。请注意，与上面提出的线性规划问题形成对比，我们在这里寻找的是一个有理数向量而不是一个整数向量。可解问题和难解问题之间的界限可能非常微妙。
- SAT. 给定 n 个布尔变量 x[1]，x[2]，…，x[N]和一个逻辑公式，是否存在一个真值变量的赋值使得公式是可满足的，即为真？例如，假设公式是
(x[1]’ + x[2] + x[3]) (x[1] + x[2]’ + x[3]) (x[2] + x[3]) (x[1]’ + x[2]’ + x[3]')
- 然后，答案是 yes，(x[1]，x[2]，x[3]) = (true，true，false)是一个证书。许多应用于电子设计自动化（EDA），包括测试和验证，逻辑综合，FPGA 布线和路径延迟分析。应用于人工智能，包括知识库推理和自动定理证明。
练习：给定两个电路 C1 和 C2，设计一个新电路 C，使得一些输入值的设置使得 C 输出为真当且仅当 C1 和 C2 等价。 - 3-SAT。 给定 n 个布尔变量 x[1]，x[2]，…，x[N]和一个逻辑公式（合取范式）的逻辑公式，每个子句恰好有 3 个不同的文字，是否存在一个真值变量的赋值使得公式可满足？
- 团。 给定 n 个人和一组成对友谊关系。是否存在一个由 k 个人组成的团或团，使得团内每对可能的人都是朋友？在绘制友谊图时很方便，其中我们为每个人包括一个节点，并连接每对朋友的边。在以下示例中，n = 11，k = 4，答案是
yes，{2, 4, 8, 9}是一个证书。 - 最长路径。 给定一组节点和节点之间的距离，是否存��一条长度至少为 L 的简单路径连接某对节点？
- 机器调度。 你的目标是在 m 台机器上处理 n 个作业。为简单起见，假设每台机器可以在 1 个时间单位内处理任何一个作业。此外，可能存在优先约束：也许作业 j 必须在作业 k 开始之前完成。你能安排所有作业在 L 个时间单位内完成吗？
调度问题有大量的应用。工作和机器可能相当抽象：为了毕业普林斯顿，你需要修读 n 门不同的课程，但不愿意在任何一个学期修读超过 m 门课程。此外，许多课程有先修课程（在修读 126 之前不能修读 COS 226 或 217，但可以同时修读 226 和 217）。你能在 L 个学期内毕业吗？ - 最短公共超字符串。 给定基因字母表{ a，t，g，c }和 N 个 DNA 片段（例如，ttt，atggtg，gatgg，tgat，atttg），是否存在一个包含 K 个或更少字符的 DNA 序列，其中包含每个 DNA 片段？假设在上面的示例中 K = 11；那么答案是
yes，atttgatggtg是一个证书。应用于计算生物学。 - 蛋白质折叠。 生物体内的蛋白质以非常特定的方式在三维空间中折叠到它们的天然状态。这种几何图案决定了蛋白质的行为和功能。最广泛使用的折叠模型之一是二维亲水-疏水（H-P）模型。在这个模型中，蛋白质是一个由 0 和 1 组成的序列，问题是将其嵌入到一个二维格子中，使得格子中相邻的 1 对数，但不在序列中（它的能量），被最小化。例如，序列 011001001110010 被嵌入到下图中，以便有 5 对新的相邻的 1（用星号表示）。
0 --- 1 --- 1 --- 0 * * | 0 --- 1 --- 1 0 | * | | 0 --- 1 * 1 * 1 | | | 0 0 --- 0
- 最小化蛋白质的 H-P 能量是 NP 难题。（Papadimitriou 等）生物学家普遍认为蛋白质折叠是为了最小化它们的能量。Levinthal 悖论的一个版本问如何可能蛋白质能够有效地解决表面上看起来棘手的问题。
- 积分。 给定整数 a[1]，a[2]，…，a[N]，以下积分是否等于 0？
- 如果你在下一门物理课程中看到这个积分，你不应该期望能够解决它。这不应该让人感到惊讶，因为在第 7.4 节中，我们考虑了一个不可判定的积分版本。
- 填字游戏. 给定一个整数 N 和一个有效单词列表，是否可以将字母分配给一个 N×N 的网格的单元格，以便所有水平和垂直单词都是有效的？如果一些方格是黑色的，像填字游戏一样，是否更容易？
- 定理. 给定一个假设的定理（比如黎曼猜想），你能否在某种形式系统（如策梅洛-弗伦克尔集合论）中使用最多 n 个符号证明它是真的？
- 俄罗斯方块.
- 扫雷.
- 正则表达式. 给定两个在一元字母表{ 1 }上的正则表达式，它们表示不同的语言吗？给定两个 NFA，它们表示不同的语言吗？也许很难确定这两个问题是否可判定，因为我们没有对一个语言中最小字符串的大小有明显的界限，而不在另一个语言中。[请注意，对于 DFA 的对应不等价问题是多项式可解的。] 我们将问题表述为不等价而不是等价的原因是，通过展示一个字符串 s，很容易检查这两个实体是否不等价。实际上，如果两个语言不同，那么最小字符串在输入大小的多项式中。因此，我们可以使用第 7.xyz 节中的高效算法来检查 s 是否被 RE 识别或被 NFA 接受。然而，要证明两个 RE 等价，我们需要一个保证所有字符串都在另一个中的论证，反之亦然。[可以设计一个（指数级）算法来测试两个 RE 或 NFA 是否等价，尽管这并不明显。]
- 旅鼠. 在游戏旅鼠的一个关卡中，是否可能引导一群绿发旅鼠生物安全到达目的地？
- 单位超立方体上的多项式最小化. 给定 N 个变量的多项式，是否最小值<= C，假设所有变量都在 0 和 1 之间。经典微积分问题：在[0, 1]上，min f(x) = ax² + bx + c。在 x = ??处的导数为 0，但最小值出现在边界处。
- 二次丢番图方程. 给定正整数 a、b 和 c，是否存在正整数 x 和 y，使得 ax² + by = c？
- 结实论. 在三维��形上哪些结实限制了一个 genus ≤ g 的表面？
- 有界后对应问题. 给定一个具有 N 张卡片的后对应问题和一个整数 K &le N，是否存在一个使用最多 K 张卡片的解？请注意，如果 K 没有限制，那么这是不可判定的。
- 纳什均衡. 合作博弈论。给定一个 2 人游戏，找到最大化玩家 1 收益的纳什均衡。是否存在多个 NE？是否存在一个帕累托最优的 NE？最大化社会福利的 NE。
- 二次同余. 给定正整数 a、b 和 c，是否存在一个小于 c 的正整数 x，使得 x² = a (mod b)？
- 3D 中的伊辛模型. 相变的简单数学模型，例如，当水结冰或冷却铁变成磁性时。计算最低能量状态是 NP 难的。如果图是平面的，则可以在多项式时间内解决，但 3D 晶格是非平面的。在被证明 NP 难之前，统计力学的圣杯已经存在了 75 年。建立 NP 完全性意味着物理学家不会再花 75 年时间试图解决不可解的问题。
- 带宽最小化. 给定一个 N×N 矩阵 A 和一个整数 B，是否可以重新排列 A 的行和列，使得 A[ij] = 0，如果|i - j| > B。对数值线性代数很有用。
- 投票和社会选择。 对于个人来说，操纵称为单一可转移选票的投票方案是 NP 难的。在 1876 年，刘易斯·卡罗尔（查尔斯·道奇森）提出的一种方案中，确定谁赢得了选举是 NP 难的。在卡罗尔的方案中，获胜者是通过在选民偏好排名中进行最少的两两相邻变化的候选人成为康德塞特赢家（在两两选举中击败所有其他候选人的候选人）。夏普利-舒比克投票权。计算Kemeny 最优聚合。
普林斯顿算法讲义（四）（4）https://developer.aliyun.com/article/1484182
