在第23篇中我们以随机快速排序和Miller-Rabin素数测试为例展示了随机化算法如何在实践中突破确定性算法的效率瓶颈。但这些讨论偏重于算法设计与分析层面。从复杂度理论的角度看随机化引入了一个根本性的问题允许算法掷硬币之后我们能多解决多少问题具体而言若允许多项式时间的概率图灵机以微小的错误概率判定语言这类语言构成的类BPP是否严格大于P大多数理论计算机科学家相信答案是“否”——即任何随机化多项式时间算法都可以被去随机化只是我们尚未找到通用的去随机化构造。本文系统阐述这一论题及其背后的理论图景。一、概率图灵机模型概率图灵机是一台被额外赋予一条只读“随机纸带”的确定性图灵机。随机纸带上预先写有一个无限的随机比特序列每个比特独立且均匀地取0或1。概率图灵机的转移函数依赖于当前状态、工作带符号和随机带上读到的比特。对于固定输入 xx 和固定的随机带内容 rr机器的行为是完全确定性的——要么接受要么拒绝。设 MM 为一台概率图灵机M(x,r)M(x,r) 表示其在输入 xx 和随机带 rr 上的输出1表示接受0表示拒绝。MM 在输入 xx 上的接受概率定义为随机带按均匀分布随机抽取时的接受频率Pr⁡[M(x)1]Pr⁡r∈{0,1}∞[M(x,r)1]Pr[M(x)1]Prr∈{0,1}∞​[M(x,r)1]MM 是多项式时间的若存在多项式 p(n)p(n)使得对任意输入 xx 和任意随机带内容 rrM(x,r)M(x,r) 在 p(∣x∣)p(∣x∣) 步内停机。基于此模型可根据错误模式定义不同的随机化复杂度类。二、RP类单侧错误的随机多项式时间RPRandomized Polynomial time是随机化复杂度类中最简单的一类它对应于具有单侧错误的蒙特卡洛算法对于“是”实例算法以显著概率接受对于“否”实例算法绝对不接受。形式化定义语言 L∈RPL∈RP当且仅当存在多项式时间概率图灵机 MM使得若 x∈Lx∈L则 Pr⁡[M(x)1]≥12Pr[M(x)1]≥21​。若 x∉Lx∈/L则 Pr⁡[M(x)1]0Pr[M(x)1]0。这里的常数 1/21/2 并非本质——任何大于 00 的常数概率均可通过多次独立运行并取逻辑或放大至任意接近 11。执行 kk 次独立运行只要有一次接受便输出接受。若 x∈Lx∈L被拒绝的概率 ≤(1/2)k≤(1/2)k随 kk 指数衰减。RP的经典成员是多项式恒等性测试Polynomial Identity Testing给定一个以代数电路表示的多元多项式 P(x1,…,xn)P(x1​,…,xn​)判断 PP 是否恒为零。随机化算法随机选择一组数值代入变量若 PP 在该点非零则输出“非零”否则输出“可能恒零”。由Schwartz-Zippel引理若非恒零多项式在随机点的值为零的概率不超过 deg⁡(P)/∣F∣deg(P)/∣F∣FF 为取值域选取足够大的域即可将错误概率压至任意小。此算法仅当多项式确实非零时可能犯错错判为恒零——“是”实例恒零多项式永远不会被拒绝。因此该问题属于RP。至今未知其是否属于P——即是否存在确定性多项式算法判定多项式恒等性。已知的包含关系为P⊆RP⊆NPP⊆RP⊆NP。第一个包含关系是因确定性算法可视为使用空随机带的退化的概率算法。第二个包含关系的原因在于对于RP机器x∈Lx∈L 的“证书”即是一条使其接受的随机带内容该证书可在多项式时间内验证模拟机器运行即可因此 L∈NPL∈NP。三、BPP类双侧有界错误的随机多项式时间RP要求“否”实例的接受概率严格为零这在许多应用如Miller-Rabin测试中过于严苛——Miller-Rabin对合数也可能以微小概率输出“素数”。BPPBounded-error Probabilistic Polynomial time放松了这一限制允许两侧都有错误但错误概率被有界常数严格控制。形式化定义语言 L∈BPPL∈BPP当且仅当存在多项式时间概率图灵机 MM使得若 x∈Lx∈L则 Pr⁡[M(x)1]≥23Pr[M(x)1]≥32​。若 x∉Lx∈/L则 Pr⁡[M(x)1]≤13Pr[M(x)1]≤31​。常数 1/31/3 和 2/32/3 同样可被放大。执行 kk 次独立运行取多数票决。Chernoff界保证错误概率随 kk 指数衰减至任意小。因此BPP常被描述为“多项式时间加随机性可判定、且错误概率可忽略不计”的问题类。已知的包含关系为RP⊆BPP⊆PSPACERP⊆BPP⊆PSPACE。第一个包含关系是因RP的错误模式是BPP的特例。第二个包含关系可通过穷举所有可能的多项式长度随机带并统计接受比例来证明空间消耗仅为多项式。我们尚不知道BPP与NP的关系——BPP可能包含NP之外的语言也可能完全位于NP之内。已知BPP ⊆⊆ P/poly即BPP语言存在多项式规模的电路族这表明BPP在非一致计算模型下并不比P更强。四、去随机化猜想BPP P理论计算机科学中最引人注目的猜想之一是BPP P。即任何随机化多项式时间算法都可以被确定性地模拟且时间代价仅多项式。直观上这等同于断言“随机性对高效计算没有本质帮助”——真正的随机比特可以被高质量的伪随机序列替代。这一猜想目前尚未被证明但在过去三十年间积累了强有力的理论证据。去随机化研究的一个核心路线是构造伪随机生成器PRG将少量真随机比特扩展为大量“看起来随机”的比特从而以确定性方式模拟随机化算法。具体而言假设存在一个从 O(log⁡n)O(logn) 个种子比特生成 nn 个输出比特的函数 GG使得对任意BPP机器用 GG 的输出替代真随机带后其接受概率的偏差不超过 εε。若 GG 本身可在多项式时间内计算则可枚举所有 2O(log⁡n)nO(1)2O(logn)nO(1) 种可能的种子对每个种子运行机器并统计多数结果从而得到BPP的确定性多项式时间算法。这种PRG的存在性被证明等价于电路复杂度下界——具体而言若存在一个可计算函数 ff其电路复杂度为 2Ω(n)2Ω(n)即需要指数规模的电路才能计算则PRG存在进而BPP P。Impagliazzo和Wigderson在1997年证明若某个判定问题需要指数规模的电路则BPP P。这一结果将去随机化与电路下界——计算复杂性中另一个核心未解难题——紧密绑定。五、ZPP与随机化类的关系全景为完整刻画随机化复杂度类的版图还需提及ZPPZero-error Probabilistic Polynomial time它对应于拉斯维加斯算法的语言类。ZPP定义为RP与coRP的交ZPPRP∩coRPZPPRP∩coRP。ZPP算法运行时间是随机变量但输出绝对正确。各随机化类之间的已知关系为P⊆ZPP⊆RP⊆BPPP⊆ZPP⊆RP⊆BPP以及 ZPP⊆NP∩coNPZPP⊆NP∩coNP。后者揭示了“零错误随机算法”与“存在高效可验证性证明”之间的关联。整体的包含关系总结为P⊆ZPP⊆RP⊆BPP⊆PSPACEP⊆ZPP⊆RP⊆BPP⊆PSPACE其中P与ZPP之间、RP与BPP之间、BPP与PSPACE之间任何一个包含关系是否为严格包含至今均未得到证明或否定。六、前沿动态与理论意义近年来去随机化研究取得了一系列重要进展。在特定问题层面Agarwal-Kayal-Saxena在2002年给出了素数判定的确定性多项式算法AKS算法将素数判定从coRP移入了P——这是去随机化在具体问题上的标志性胜利。在一般性理论层面Cecil、Murray和Vadhan等人在2018年前后推进了几乎对数种子长度的PRG构造逐步逼近了完全去随机化BPP P的目标。去随机化研究的深层次意义在于它试图回答“随机性是否确实是计算资源”这一哲学问题。若BPP P成立则意味着任何在高概率下正确的多项式时间算法都可以被等效的确定性多项式时间算法替代——随机性在计算效率上并不是一种“本质资源”而是一种可以被精巧的确定性构造模拟的便利工具。反之若BPP ⊋⊋ P则说明“允许抛硬币”确实扩展了多项式时间内可解问题的边界这将深刻改变我们对计算能力的理解。七、总结与展望RP和BPP分别刻画了单侧和双侧错误的多项式时间随机化计算能力。它们位于P与PSPACE之间与NP的相对位置至今未知。去随机化猜想——BPP P——虽未被完全证明但在伪随机生成器与电路下界之间建立的深刻联系已使之成为理论计算机科学中结构最清晰、进展最可期的核心开放问题之一。随机化不仅渗透到时间复杂度的研究也在空间复杂度和交互式计算中扮演关键角色。下一篇我们将进入交互式证明系统这一更加精彩的理论领域当验证者可以与证明者进行多轮交互并抛掷随机硬币时可验证的语言类从NP一跃扩展到了IP PSPACE。零知识证明——密码学中最迷人的概念之一——也将在这套框架中获得其严格的形式化定义。