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

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

随机算法的错误类型

设 $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 算法，可交替运行二者，接受可靠的单侧结论，得到零错误的期望多项式时间算法。因此

$$\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$ 的常数。

错误率放大

独立重复 $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 极小极大原理

随机算法是确定性算法上的分布。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)].$$

若研究有界错误算法，应固定查询或通信预算 $t$，把上式中的 cost 换成出错指示量，并让 $A$ 遍历预算内的确定性算法。此时 $R$ 是这些算法的分布，等式比较最坏输入错误率与最难分布上的平均错误率。若改用期望运行成本或零错误算法，必须重新明确策略集合和收益，不能混用这些版本。

分布复杂度

distributional problem $(L,\mathcal D)$ 同时给出 language 与可采样分布族。一种直接的平均时间定义是

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

但这一“期望时间为多项式”的定义在某些归约和多项式开销变换下不够稳健。平均复杂度理论还使用适当正数阶矩或尾部条件等定义；引用平均困难性结论时必须说明采用哪一种。

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

最坏情况与平均情况

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

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

伪随机生成器

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，模拟算法需要的随机性。

困难性与随机性

复杂函数的 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？