第一章：计算问题与编码

复杂度不是算法文本的属性，而是算法相对于一族输入所消耗的资源。讨论算法前，需要先规定实例集合、合法输出、输入长度和错误标准。

Decision problem 与 language

decision problem 对每个输入输出一个 bit。固定编码后，它可以表示为 language

L\subseteq\Sigma^*,

其中 $x\in L$ 表示答案为 yes。

例如无向图连通性可写为

\mathrm{USTCON}=\{\langle G,s,t\rangle:\text{$G$ 中存在从 $s$ 到 $t$ 的路径}\}.

language 表示法把图、公式和程序统一为字符串，使图灵机和归约能够处理任意离散对象。代价是必须说明编码。合理编码通常要求相互之间可以高效转换；否则复杂度结论可能只是编码造成的。

Function problem

function problem 要求计算

f:\Sigma^*\to\Sigma^*.

排序、最大流值和矩阵乘法都属于此类。函数可能是偏函数，此时只对定义域内输入规定输出。

decision 与 function 不能无条件互换。若能计算最优值，通常可以回答阈值 decision；反向从 decision 恢复完整输出，往往还需要 self-reduction。例如 SAT 的判定算法可以逐个固定变量并重复查询，从而构造一个满足赋值，查询次数为多项式。

函数复杂度还需计入输出长度。若输出本身有指数长度，则不存在关于输入长度的多项式总运行时间；此时可采用 polynomial delay、output-sensitive complexity 等度量。

Search relation

search problem 用二元关系

R\subseteq\Sigma^*\times\Sigma^*

描述。给定 $x$ ，目标是输出任意满足 $(x,y)\in R$ 的 witness $y$ 。同一输入可以有多个正确输出，也可能不存在输出。

例如

R_{\mathrm{SAT}}(\varphi,a)=1

表示赋值 $a$ 满足公式 $\varphi$ 。算法的正确性条件包括：

soundness：输出的 $y$ 必须满足关系；
completeness：若存在 witness，算法必须按规定概率找到一个；
资源界：通常要求 $|y|$ 和验证时间受 $|x|$ 的多项式约束。

搜索关系比函数更适合描述可行解、局部最优和博弈均衡，因为这些问题没有自然的唯一输出。

Total search

若对每个输入 $x$ 都存在某个 $y$ 使 $(x,y)\in R$ ，则称为 total search problem。其存在性常来自组合定理：

Pigeonhole Principle 导出碰撞或端点的存在；
parity argument 导出图中另一个奇度顶点；
potential argument 保证局部改进过程终止；
Brouwer fixed-point theorem 保证近似不动点存在。

totality 排除了“无 witness”的实例，但不自动给出高效构造。这一差异形成 TFNP 及其 PPAD、PLS、PPP 等子类。

Promise problem

promise problem 由互不相交的 yes/no 集合组成：

\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}}).

算法只需在 $x\in\Pi_{\mathrm{yes}}\cup\Pi_{\mathrm{no}}$ 时满足正确性；对违反 promise 的输入不作规定。

近似问题、编码问题和量子复杂度经常自然地产生 promise。例如区分某量 $q(x)\le 1/3$ 与 $q(x)\ge 2/3$ ，而不要求处理间隙区域。

promise 不能被忽略。一个归约必须把有效实例映射为目标 promise 内的实例，否则不能传递正确性。

Optimization problem

优化问题可以写为实例 $x$ 、可行解集合 $F(x)$ 和目标函数 $c(x,y)$ 。常见目标是

\min_{y\in F(x)}c(x,y).

需要区分：

feasibility：构造任意 $y\in F(x)$ ；
exact optimization：构造最优解；
value problem：只输出最优值；
threshold decision：判断最优值是否不超过 $k$ ；
approximation：满足乘法或加法误差界。

这些版本经常可以相互归约，但归约开销和数值编码必须显式分析。强多项式算法、伪多项式算法和 FPTAS 的区别都与数值大小和编码长度有关。

Distributional problem

最坏情况复杂度把每个长度为 $n$ 的输入都纳入上界。若关心输入来源，需要同时规定分布族

\mathcal D=\{D_n\}_{n\ge 1}.

distributional problem 记为 $(L,\mathcal D)$ 。平均运行时间、平均错误率和 high-probability bound 是不同保证：

\mathbb E_{x\sim D_n}[T(x)],\qquad \Pr_{x\sim D_n}[T(x)>t(n)].

只说“随机输入上很快”没有完整含义，必须说明分布是否可采样、是否与算法独立，以及结论对分布扰动是否稳定。

参数与输入长度

复杂度函数的自变量通常是编码长度 $n=|x|$ ，也可以同时使用结构参数 $k$ ：

T(n,k)=f(k)n^{O(1)}.

parameterized complexity 研究参数依赖是否可以从指数项中分离。fine-grained complexity 则保留更精确指数，例如区分 $n^2$ 与 $n^{2-\varepsilon}$ ，并通过 SETH 等假设建立条件 lower bound。

使用数值参数时尤其要区分值与位数。对二进制整数 $N$ 执行 $O(N)$ 步，对输入长度而言是 $2^{O(|N|)}$ 。

编码不变性

若两个编码 $e_1,e_2$ 满足：

均可在多项式时间内验证和转换；
转换后的长度至多多项式增长；
不依赖问题答案进行编码，

则 $\mathsf P$ 、 $\mathsf{NP}$ 等粗粒度多项式类通常对二者不敏感。空间复杂度、流式算法和 fine-grained complexity 对编码更敏感，因此仍需保留具体表示。

本章自测

为什么“输出所有满足赋值”不可能仅按公式长度获得多项式总时间？
search relation 的正确性与 decision problem 有何不同？
promise problem 的归约为什么必须保持 promise？
伪多项式时间中的“多项式”是关于哪个量？
平均运行时间小是否能推出运行时间以高概率较小？

下一章：计算模型 →

第一章：计算问题与编码 ​

Decision problem 与 language ​

Function problem ​

Search relation ​

Total search ​

Promise problem ​

Optimization problem ​

Distributional problem ​

参数与输入长度 ​

编码不变性 ​

本章自测 ​