平均情形复杂性与分布归约

形式陈述

问题与输入分布一起给定

本页固定二进制可判定语言 $L$ 与分布族 $D=(D_n)_{n\ge1}$ ，其中 $D_n$ 是长度恰为 $n$ 的字符串上的概率分布。二者组成分布问题 $(L,D)$ 。

算法 $A$ 是确定性的，要求对每个输入停机并正确判定 $L$ ，包括分布质量为零的输入。记运行时间 $T_A(x)\ge1$ ；随机性只来自输入 $X_n\sim D_n$ 。分布族是数学模型的一部分，下面的保持定理不额外要求能够高效抽样或计算它；讨论专门的分布复杂性类时，需要另加这类条件。

采用现代按长度分布的 Levin 平均时间口径：若存在固定 $\varepsilon>0$ 和多项式 $p$ ，使

\forall n\ge1,\qquad \mathbb E_{X_n\sim D_n}[T_A(X_n)^\varepsilon]\le p(n), \tag{1}

则称 $A$ 对 $D$ 具有平均多项式运行时间。存在这样的处处正确判定器时，本页称 $(L,D)\in\mathrm{AvgP}$ 。这是全正确、按长度取正阶矩的约定，不是允许小概率答错的启发式约定。[1,2]

式 (1) 中的期望是

\sum_{x\in\{0,1\}^n}D_n(x)T_A(x)^\varepsilon.

指数 $\varepsilon=1$ 对应期望运行时间为多项式，是对这份算法更强的要求；一般允许某个较小正指数。若文献把右侧写成 $O(n)$ ，所得存在性条件不变：将 $p(n)$ 上界成 $Cn^k$ ，取整数 $k\ge1$ ，由凹函数形式的 Jensen 不等式，

\mathbb E[T_A^{\varepsilon/k}] \le(\mathbb E[T_A^\varepsilon])^{1/k} \le C^{1/k}n.

一种明确的分布归约接口

下面只使用输出长度由输入长度决定的 many-one 归约。从 $(L,D)$ 到 $(K,E)$ 的归约 $f$ 满足：

$f$ 是对全部输入都可在多项式时间内计算的全函数，并且 $x\in L\iff f(x)\in K$ 。
有可计算的整数函数 $m(n)$ 及多项式 $s$ ，使 $|f(x)|=m(n)$ 对所有 $|x|=n$ 成立，且 $1\le m(n)\le s(n)$ 。
对某个多项式 $q$ 、每个 $n$ 及每个 $y\in\{0,1\}^{m(n)}$ ，有概率支配 $Q_n(y):=\sum_{\substack{x\in\{0,1\}^n\\f(x)=y}}D_n(x) \le q(n)E_{m(n)}(y). \tag{2}$

$Q_n$ 是先按 $D_n$ 抽输入、再计算 $f$ 得到的推前分布。它把所有前像的质量相加。条件 (2) 也要求用于目标概率为零的点，此时强制 $Q_n(y)=0$ ，防止归约把正质量送到目标保证之外。

前两项加强了普通多项式时间归约的长度接口；第三项控制概率如何改变。这是用于完整推导保持性的一个充分模型，没有声称涵盖文献中全部可变长度、随机化或 oracle 归约。[1,2]

保持定理。 若存在上述归约，且 $(K,E)\in\mathrm{AvgP}$ ，则 $(L,D)\in\mathrm{AvgP}$ 。这样的归约还对复合封闭。

直觉

最坏时间归约只关心实例翻译正确且翻译本身足够快。平均时间还要问：目标算法平时很少遇到的慢实例，会不会被翻译器频繁制造出来？一个目标点虽然概率极小，却可能收集指数多个源实例的质量。

式 (2) 保证目标的任何慢区域在翻译后最多被放大一个多项式倍数。目标算法可以在稀有区域耗费很长时间，只要运行时间尾部与区域概率具有合适的权衡；归约需要一起保存这种权衡。

尾概率与正阶矩等价，但指数可以改变

由 Markov 不等式，式 (1) 推出对每个 $t\ge1$ ，

\Pr[T_A(X_n)\ge t] \le\frac{\mathbb E[T_A^\varepsilon]}{t^\varepsilon} \le\frac{p(n)}{t^\varepsilon}. \tag{3}

反过来，假设某个固定 $\alpha>0$ 满足尾界 $\Pr[T_A\ge t]\le p(n)t^{-\alpha}$ 。对任意 $0<\delta<\alpha$ ，用非负变量的尾积分公式，

\begin{aligned} \mathbb E[T_A^\delta] &=\int_0^\infty\Pr[T_A^\delta>u]\,du\\ &\le1+p(n)\int_1^\infty u^{-\alpha/\delta}\,du\\ &=1+p(n)\frac{\delta}{\alpha-\delta}. \end{aligned}

取 $\delta=\alpha/2$ ，便得到多项式矩界。这证明两种存在性判据等价；尾界指数 $\alpha$ 并不直接保证同阶矩也具有相同的统一界。

为什么允许正指数能承受多项式慢化

假设另一实现满足

T_B(x)\le Cn^a(T_A(x)+1)^b,

其中 $C>0$ 、 $a\ge0$ 、整数 $b\ge1$ 都固定。若 $A$ 满足式 (1)，令 $\eta=\min\{\varepsilon,1\}/b$ ，则 $b\eta\le1$ 。利用 $(u+v)^\theta\le u^\theta+v^\theta$ 对 $0<\theta\le1$ 成立，及 $T_A\ge1$ ，有

\begin{aligned} \mathbb E[T_B^\eta] &\le C^\eta n^{a\eta}\mathbb E[(T_A+1)^{b\eta}]\\ &\le C^\eta n^{a\eta}\bigl(1+\mathbb E[T_A^\varepsilon]\bigr). \end{aligned}

右侧仍由多项式控制。于是合理机器模拟造成的多项式开销可以吸收，只需相应减小矩指数。单独要求 $\mathbb ET_A$ 为多项式，就没有这种对任意多项式慢化的稳健性。

例子与边界

稀有慢分支的完整成本

在均匀输入 $U_n$ 下，考虑给定的耗时表

T_A(x)= \begin{cases} 2^n,&x=0^n,\\ n^2,&x\ne0^n. \end{cases}

可以把它理解为一份正确算法在一个指定输入上额外等待；常数级实现开销不影响下面的渐近区别。这个例子讨论一份算法的耗时分配，不声称 $0^n$ 本身难以求解。

异常输入的概率为 $2^{-n}$ ，故

\mathbb ET_A=(1-2^{-n})n^2+1.

若每个输入上的成本都平方， $T_B=T_A^2$ ，则

\mathbb ET_B=(1-2^{-n})n^4+2^n.

原本异常分支只贡献一，平方后却贡献 $2^n$ 。但仍有 $\mathbb E[T_B^{1/2}]=\mathbb ET_A$ ，所以两种耗时都满足正阶矩条件。

取 $n=10$ ，可直接复算：

量	原耗时	平方后耗时
异常输入概率	$1/1024$	$1/1024$
异常输入成本	$1024$	$1048576$
异常部分的期望贡献	$1$	$1024$
全部输入的期望	$100.90234375$	$11014.234375$

“小概率”本身不能删除一项成本；还要乘以发生时的代价。

合并前像的有效归约

令源与目标语言都为“首位是 1”，输入分布都均匀。对 $n\ge2$ 定义

f(x_1\cdots x_{n-1}x_n)=x_1\cdots x_{n-1}0.

它在线性时间内保留首位和长度；长度一时取恒等映射。每个末位为零的目标有两个前像，所以

Q_n(y)= \begin{cases} 2^{-(n-1)},&y_n=0,\\ 0,&y_n=1, \end{cases} \qquad Q_n(y)\le2U_n(y).

$n=2$ 时的全部质量如下：

目标 $y$	前像	$Q_2(y)$	$U_2(y)$	放大倍数
$00$	$00,01$	$1/2$	$1/4$	$2$
$01$	无	$0$	$1/4$	$0$
$10$	$10,11$	$1/2$	$1/4$	$2$
$11$	无	$0$	$1/4$	$0$

逐个比较一个源点与一个目标点会漏掉这个二倍因子；归约不要求单射，因而必须计算前像质量和。

正确的 Karp 归约仍可能破坏平均保证

仍用首位语言和均匀分布，改成

g(x)=x_1\,0^{n-1}.

这是正确、线性时间且保持长度的普通归约。但它只产生 $0^n$ 与 $10^{n-1}$ ，各有概率 $1/2$ ；每点在目标均匀分布下的概率却是 $2^{-n}$ 。放大倍数为 $2^{n-1}$ ，不存在统一的多项式支配因子。

具体取一个正确目标判定器，在这两个点上花费 $2^n$ 、其他点上花费 $n^2$ 。其均匀期望为

(1-2^{1-n})n^2+2,

仍为多项式。可是组合 $A(g(x))$ 在每个源输入上都进入慢分支，任何固定正阶矩都是 $2^{\varepsilon n}$ ，不再具有平均多项式保证。

这证明普通归约不能自动传递给定目标求解器的平均性能。两个语言本身仍然容易，直接查看首位即可判定；例子没有制造一个平均困难语言。

推论与应用

归约保持定理的完整证明

设目标判定器 $A$ 满足 $\mathbb E_{E_m}[T_A^\varepsilon]\le p(m)$ 。源算法先计算 $f(x)$ ，再运行 $A$ 。归约正确性保证它对每个输入都正确停机。

先按直接顺序运行的模型计费，令 $T_B(x)\le r(n)+T_A(f(x))$ ，其中 $r$ 控制翻译开销。若具体机器模拟还有多项式开销，前面的慢化引理允许再吸收它。取 $\eta=\min\{\varepsilon,1\}$ ，有

\begin{aligned} \mathbb E_{D_n}[T_B^\eta] &\le r(n)^\eta+\sum_y Q_n(y)T_A(y)^\eta\\ &\le r(n)^\eta+q(n)\sum_yE_{m(n)}(y)T_A(y)^\eta\\ &\le r(n)^\eta+q(n)p(m(n)). \end{aligned}

最后一步用 $T_A\ge1$ 和 $\eta\le\varepsilon$ 。输出长度 $m(n)$ 多项式有界，因此右侧也是 $n$ 的多项式，保持性得证。对任何目标集合 $S$ ，同样逐点求和得到 $Q_n(S)\le q(n)E_{m(n)}(S)$ ，解释了慢区域的概率如何受到控制。

复合归约的概率因子

若第二个归约 $g$ 把长度 $m$ 送到 $\ell(m)$ ，支配因子为 $q_g(m)$ ，则对最终目标点 $z$ ，

\begin{aligned} \Pr[g(f(X_n))=z] &=\sum_{y:g(y)=z}Q_n(y)\\ &\le q_f(n)\sum_{y:g(y)=z}E_{m(n)}(y)\\ &\le q_f(n)q_g(m(n))H_{\ell(m(n))}(z). \end{aligned}

两个多项式因子相乘、输出长度经过多项式复合，仍符合接口。算法时间和判定正确性则沿普通归约复合传递。

这些证明说明平均情形分析必须同时保存三项：判定语义、计算成本、输入质量。把某个现实工作负载换成均匀位串，或只证明最坏情况下的 NP 困难性，都没有自动处理第三项。

参考资料

[1] Leonid A. Levin, Average Case Complete Problems, SIAM Journal on Computing 15(1), 1986, pp. 285–286，第一页 Conventions：平均多项式时间、分布支配与归约复合。原文采用单个输入分布，本页采用按长度分布族。
[2] Andrej Bogdanov and Luca Trevisan, Average-Case Complexity，2021 年修订稿，§2.1；§2.2.1，Definitions 3–4、Proposition 5，printed pp. 14–15；§3.1，Definition 17、Lemma 18，pp. 23–24。本页固定定长、处处正确接口，并直接用矩估计展开保持证明；概率支配明确要求覆盖零质量目标点。

形式陈述 ​

问题与输入分布一起给定 ​

一种明确的分布归约接口 ​

尾概率与正阶矩等价，但指数可以改变 ​

为什么允许正指数能承受多项式慢化 ​

稀有慢分支的完整成本 ​

合并前像的有效归约 ​

正确的 Karp 归约仍可能破坏平均保证 ​

归约保持定理的完整证明 ​

复合归约的概率因子 ​

反向链接