第九章：随机化与平均复杂度

随机算法在固定输入上对内部随机位取概率。平均复杂度则对输入分布取平均。两种概率来源必须分别建模。

随机算法的错误类型

设 $M(x;r)$ 使用随机串 $r$。

RP

one-sided error：

$$\begin{aligned} x\in L&\Rightarrow \Pr_r[M(x;r)=1]\ge \frac12,\\ x\notin L&\Rightarrow \Pr_r[M(x;r)=1]=0. \end{aligned}$$

接受结果可靠，拒绝可能是未找到证据。

coRP

错误方向与 RP 相反。若算法同时具有 RP 与 coRP 性质，可通过 Las Vegas 形式得到

$$\mathsf{ZPP}=\mathsf{RP}\cap\mathsf{coRP}.$$

ZPP 算法永不输出错误答案，但运行时间是期望多项式。

BPP

two-sided bounded error：

$$\Pr_r[M(x;r)=L(x)]\ge\frac23$$

对每个输入 $x$ 成立。常数 $2/3$ 可替换为任意严格大于 $1/2$ 的常数。

Error amplification

独立重复 $k$ 次并取多数，Chernoff bound 给出错误率

$$\Pr[\text{majority wrong}]\le e^{-\Omega(k)}.$$

取 $k=O(\log n)$ 可将错误降至 $1/\operatorname{poly}(n)$，只增加对数因子。放大证明依赖独立或足够弱相关的随机试验。

当算法要在多项式多个事件上同时成功时，通常先将单次错误降至逆多项式，再使用 union bound。

随机位也是资源

算法可能只需 pairwise independent hash，而不需要完整独立随机串。减少随机位可降低实现和 derandomization 成本。

randomness complexity 计算使用的随机 bit 数。若算法只使用 $O(\log n)$ 随机位，可以枚举全部随机串并确定性模拟，产生多项式时间算法。因此，显著随机优势通常需要更多随机位或其他资源限制。

Yao minimax principle

随机算法是确定性算法上的分布。Yao principle 将最坏输入上的 randomized lower bound 转化为某个输入分布上所有 deterministic algorithm 的平均 lower bound。

在固定成本的有限模型中，minimax 等式可写为

$$\min_R\max_x \mathbb E[\operatorname{cost}(R,x)] = \max_D\min_A \mathbb E_{x\sim D}[\operatorname{cost}(A,x)].$$

证明 randomized lower bound 时，可以选择一个困难分布 $D$，再分析任意确定性算法。该方法广泛用于通信和查询复杂度。

Distributional complexity

distributional problem $(L,\mathcal D)$ 同时给出 language 与可采样分布族。平均多项式时间不能只用

$$\mathbb E[T(x)]\le\operatorname{poly}(n)$$

粗略描述，因为极小概率的巨大运行时间在归约和组合下可能不稳定。平均复杂度理论通常采用更稳健的尾部定义。

average-case reduction 除保持答案外，还需保证输出分布不会把过多概率集中到目标分布中的稀有实例。

Worst-case 与 average-case

最坏情况困难不自动推出自然分布困难。一个问题可以只有极少数构造性困难实例。密码学需要攻击者在密钥生成分布上难以成功，因此依赖 average-case hardness。

某些代数问题存在 worst-case-to-average-case reduction：若能解决足够多随机实例，就能解决任意实例。lattice cryptography 的若干基础问题具有这类联系，但具体参数和分布是定理不可缺少的部分。

Pseudorandom generator

PRG 将短 seed 扩展为长字符串：

$$G:\{0,1\}^s\to\{0,1\}^m,\qquad s<m,$$

并要求受限计算模型无法区分 $G(U_s)$ 与均匀分布 $U_m$。

“看起来随机”总是相对于 distinguisher class 定义。无界算法可以枚举 $G$ 的 range，并立即区分，因为其大小至多 $2^s$。

PRG 同时服务两个目标：

• cryptography：对多项式时间攻击者不可区分；
• derandomization：枚举较短 seed，模拟算法需要的随机性。

Hardness versus randomness

复杂函数的 circuit lower bound 可以用于构造 PRG，PRG 又可确定性模拟随机算法。该联系形成 hardness-versus-randomness 范式：足够强的 worst-case hardness 假设可推出

$$\mathsf{BPP}=\mathsf P.$$

无条件是否 $\mathsf{BPP}=\mathsf P$ 未知，但通常猜测随机性不增加多项式时间判定能力。即使类相等，随机算法仍可能更简单或具有更好的实际常数。

随机性不能替代模型说明

报告随机算法时需要说明：

• 概率对输入还是内部随机位取得；
• 是期望时间还是 high-probability 时间；
• 错误是 one-sided、two-sided 还是 zero-error；
• 对每个输入成立，还是仅对 $x\sim D_n$；
• 随机位是否独立；
• adversary 是否能观察或适应随机选择。

oblivious adversary 与 adaptive adversary 下的结论可能不同。

本章自测

1. BPP 的概率保证为何是对每个固定输入成立？
2. ZPP 的“零错误”与运行时间保证如何组合？
3. 为什么 $O(\log n)$ 随机位通常可以被穷举消除？
4. Yao principle 如何把 randomized lower bound 转成 distributional lower bound？
5. PRG 的不可区分性为什么必须指定 distinguisher class？

上一章：搜索、计数与证明 · 下一章：通信复杂度 →