离散优化：复杂度理论(Complexity)⚓︎

约 2101 个字 3 行代码预计阅读时间 7 分钟总阅读量次

本章导读

求解方法分类：精确方法求最优，启发式方法求可行，近似方法有理论保证
大 O 表示法：忽略常数，关注主导项，描述算法随规模增长的趋势
P vs NP：P 类可多项式时间求解，NP 类仅可多项式时间验证
NP-完全性：NP 中最难的问题，所有 NP 问题都可约化为它
NP-难：优化问题版本的 NP-完全问题

1. 引言 (Introduction)⚓︎

1.1 求解方法的分类⚓︎

优化问题的求解方法主要分为以下三类：

精确方法 (Exact Methods)

将问题求解至最优性 ("solves a problem to optimality")

启发式方法 (Heuristic Methods)

在可接受的计算时间内寻找好的解，无法保证所找到的解是最优的，在某些情况下甚至无法找到可行解 ("looks for a good solution within an acceptable computing time, without being able of ensuring the optimality of the solution found and, in some cases, without being able of finding a feasible solution")

近似方法 (Approximation Methods)

该术语专用于那些可以获得理论结果的启发式方法，例如：

最坏情况下的最大相对误差 (maximum relative error in the worst case)
期望误差 (expected error)
等等

1.2 优化问题的复杂度⚓︎

当面对同一问题的不同方法时，自然会问哪个是最好的。

算法 (Algorithm) 是通用的、逐步解决问题的程序：

\[
\boxed{\text{algorithm} = \text{method} + \text{data structure}}
\]

复杂度理论 (Complexity theory) 研究算法解决计算问题所需的资源（例如时间和内存），关注问题之间的关系，并研究具有可比计算需求的问题类 (classes of problems)，即复杂度类 (complexity classes)。

"Complexity theory studies the resources (e.g., time and memory) needed by an algorithm to solve a computational problem"

2. 算法的复杂度 (Complexity of Algorithms)⚓︎

2.1 基本概念⚓︎

概念	定义	英文原文
问题实例 (Instance)	特定的问题参数值	"particular values for all the problem parameters"
问题规模 (Size)	描述实例所需的输入数据量（编码所有数据所需的位数）	"amount of input data needed to describe the instance (number of bits needed for encoding all data)"
时间复杂度 (Time-complexity)	解决给定规模的任何实例所需的最大计算步骤数	"maximal number of computational steps that it takes to solve any instance of the considered problem of a given size"

最坏情况分析 (Worst-case analysis)：作为问题规模函数的步骤数上界

"upper bound on the number of steps as a function of the problem size"

3. 大 O 表示法 (Big O Notation)⚓︎

3.1 示例分析⚓︎

考虑如下程序（矩阵加法）：

for i := 1 to n do
  for j := 1 to n do
    cij := aij + bij;

精确步骤数依赖于具体实现，难以计算
简化原则：
忽略常数
每个操作计为一步
当问题规模足够大时，只考虑主导项 (most dominant term)

3.2 阶的表示法 (Order Notation)⚓︎

研究给定算法 \(A\) 的复杂度 \(C_A\) 作为规模 \(s\) 的函数，即研究 \(C_A = f(s)\) 的阶 (order)，当 \(s \to \infty\) 时。

定义：给定定义域为自然数的两个函数 \(f\) 和 \(g\)，如果存在正常数 \(k\) 和 \(n_0\)，使得对所有 \(s \geq n_0\) 都有：

\[
f(s) \leq kg(s)
\]

则称 \(f\) 的阶低于或等于 \(g\) 的阶，记作：

\[
f = O(g)
\]

3.3 算法分类⚓︎

多项式时间算法 (Polynomial time algorithm)

复杂度为 \(O(p(s))\)，其中 \(p(s)\) 是 \(s\) 的多项式函数

示例：\(O(n^2)\)、\(O(nm)\)、\(O(m \log C)\)

指数时间算法 (Exponential time algorithm)

复杂度无法被规模 \(s\) 的任何多项式所界定

示例：\(O(2^n)\)、\(O(n!)\)

4. 多项式与指数时间复杂度的比较⚓︎

假设执行单步操作耗时 \(1.0 \times 10^{-6}\) 秒（1 微秒）：

复杂度函数	\(n=10\)	\(n=20\)	\(n=30\)	\(n=40\)	\(n=50\)	\(n=60\)
\(n\)	\(0.00001\) s	\(0.00002\) s	\(0.00003\) s	\(0.00004\) s	\(0.00005\) s	\(0.00006\) s
\(n^2\)	\(0.0001\) s	\(0.0004\) s	\(0.0009\) s	\(0.0016\) s	\(0.0025\) s	\(0.0036\) s
\(n^3\)	\(0.001\) s	\(0.008\) s	\(0.027\) s	\(0.064\) s	\(0.125\) s	\(0.216\) s
\(n^5\)	\(0.1\) s	\(3.2\) s	\(24.3\) s	\(1.7\) min	\(5.2\) min	\(13.0\) min
\(2^n\)	\(0.001\) s	\(1.0\) s	\(17.9\) min	\(12.7\) days	\(35.7\) years	\(365.6\) centuries
\(n!\)	\(3.6\) s	\(771.5\) centuries	\(8.4 \times 10^{16}\) centuries	\(2.6 \times 10^{32}\) centuries	\(9.6 \times 10^{48}\) centuries	\(2.6 \times 10^{66}\) centuries

5. 技术进步对算法效率的影响⚓︎

5.1 硬件加速的效果对比⚓︎

下表展示了在当前计算机、快 100 倍的计算机、快 1000 倍的计算机上，1 小时内可解决的最大问题实例规模：

时间复杂度函数	当前计算机	速度快 100 倍	速度快 1000 倍
\(n\)	\(N_1\)	\(100N_1\)	\(1000N_1\)
\(n^2\)	\(N_2\)	\(10N_2\)	\(31.6N_2\)
\(n^3\)	\(N_3\)	\(4.64N_3\)	\(10N_3\)
\(n^5\)	\(N_4\)	\(2.5N_4\)	\(3.98N_4\)
\(2^n\)	\(N_5\)	\(N_5 + 6.64\)	\(N_5 + 9.97\)
\(3^n\)	\(N_6\)	\(N_6 + 4.19\)	\(N_6 + 6.29\)

关键观察

对于多项式时间算法，硬件速度提升带来乘法级（或接近乘法级）的问题规模增长
对于指数时间算法，硬件速度 100 倍或 1000 倍的提升仅能线性增加可处理的问题规模（仅增加常数项）

这正是为什么面对 NP-难问题时，单纯依赖硬件升级是徒劳的。

6. 复杂度类：\(\mathcal{P}\) 和 \(\mathcal{NP}\)⚓︎

6.1 判定问题 (Decision Problems)⚓︎

NP 完全性理论仅适用于判定问题，这类问题只有两种可能的答案："是"（yes）或"否"（no）。

示例：背包问题 (Knapsack Problem) 的判定形式

实例 (Instance)：\(n, c \in \mathbb{Z}\), \(p, w \in \mathbb{Z}^n\)
结构 (Structure)：是否存在 \(x \in \{0,1\}^n\) 使得 \(wx \leq c\) 且 \(px \geq k\)，其中 \(k \in \mathbb{Z}\) 是给定参数
若 \(k \geq z^* + 1\)（\(z^*\) 为最优解的值），则上述判定问题的答案为否

6.2 复杂度类定义⚓︎

\(\mathcal{P}\) 类 (Class \(\mathcal{P}\))

存在算法能在多项式时间 (polynomial time) 内对任何实例确定答案是"是"或"否"的问题集合

即所需计算步骤数被问题规模的多项式函数所界定

"Problems for which there exists an algorithm that, for any instance, determines in polynomial time whether the answer is yes or no"

\(\mathcal{NP}\) 类 (Class \(\mathcal{NP}\))

存在算法能在多项式时间内验证 (checking/verifying) 给定结构，从而验证"是"的答案的问题集合

"Problems for which there exists an algorithm checking of a given structure in a polynomial time, thereby verifying the yes answer"

示例说明：

对于背包问题，若给定一个解 \(x'\)，验证 \(wx' \leq c\) 和 \(px' \geq k\) 只需 \(O(n)\) 次加法和比较
但要验证"否"的答案（即证明不存在这样的 \(x\)），最坏情况下需要检查全部 \(2^n\) 个二进制向量

6.3 基本关系⚓︎

\[
\mathcal{P} \subseteq \mathcal{NP}
\]

由于许多著名的组合问题属于 \(\mathcal{NP}\) 但尚未知是否属于 \(\mathcal{P}\)，学术界普遍猜想：

\[
\boxed{\mathcal{P} \neq \mathcal{NP}}
\]

这是计算机科学中最重要的未解之谜之一。

7. \(\mathcal{NP}\)-完全与 \(\mathcal{NP}\)-难⚓︎

7.1 问题间的可约化性 (Reducibility)⚓︎

计算复杂度理论确立了某些组合问题具有相同的难度。

定义 1：可约化 (Reducible)

问题 \(P_1\) 可约化为问题 \(P_2\)，记作 \(P_1 \propto P_2\)，如果：

\(P_1\) 可视为 \(P_2\) 的特例；或更正式地，
对 \(P_1\) 的任何实例，可在多项式时间 (polynomial time) 内构建 \(P_2\) 的对应实例，使得解决后者也解决前者。

"\(P_1\) can be considered as a special case of \(P_2\), or more formally, if for any instance of \(P_1\), a corresponding instance of \(P_2\) can be constructed in polynomial time such that solving the later solves the former as well"

7.2 \(\mathcal{NP}\)-完全问题 (\(\mathcal{NP}\)-complete)⚓︎

定义：问题 \(P_2\) 是 \(\mathcal{NP}\)-完全的，如果：

\(P_2 \in \mathcal{NP}\)；
对所有 \(P \in \mathcal{NP}\)，都有 \(P \propto P_2\)（即 \(\mathcal{NP}\) 中所有问题都可约化为 \(P_2\)）。

历史注记：

第一个被证明是 \(\mathcal{NP}\)-完全的问题是可满足性问题 (Satisfiability Problem)：询问布尔公式集是否存在布尔变量的真值赋值。

重要推论

如果某个 \(\mathcal{NP}\)-完全问题存在多项式时间算法，则可用它在多项式时间内解决 \(\mathcal{NP}\) 中的任何问题，从而证明 \(\mathcal{P} = \mathcal{NP}\)！

7.3 \(\mathcal{NP}\)-难问题 (\(\mathcal{NP}\)-hard)⚓︎

\(\mathcal{NP}\)-难问题定义

若一个优化问题 (optimization problem) 对应的判定问题 (decision problem) 是 \(\mathcal{NP}\)-完全的，则该优化问题是 \(\mathcal{NP}\)-难的。

"An optimization problem is \(\mathcal{NP}\)-hard if the corresponding decision problem is \(\mathcal{NP}\)-complete"

8. 注释与参考文献 (Notes and References)⚓︎

Garey and Johnson ¹ 的著作被广泛认为是计算复杂度理论的优秀指南。

Garey, M. R. and D. S. Johnson, 1979: Computers and Intractability: A Guide to the Theory of \(\mathcal{NP}\)-Completeness. Freeman, San Francisco. ↩