Adleman 1978：可放大的随机性怎样被多项式忠告替换

破除误解：小电路不是确定性算法，两条印刷也不是同一句话#

第一层误解把标题听成「因此 $P=\mathrm{BPP}$」，或听成已经给出一台对所有长度通用的确定性多项式时间机器。原文给的是非均匀上界。电路族可以对每个输入长度换一张图，不要求存在一台自己会造出所有图的多项式时间图灵机。忠告字符串 $\alpha_n$ 只依赖长度 $n$，长度为 $n$ 的所有输入共用同一条字。若这条字还能被一台多项式时间机器自己写出来，均匀算法就会吞掉 $\mathrm{BPP}$，那才是 $P=\mathrm{BPP}$。阿德尔曼的存在性弱得多：每个长度「在那儿」有一条好硬币，造硬币的手续却不必均匀可算。把「有一张表」听成「有一套对所有 $n$ 都管用的程序」，会把一次非均匀上界收成一次去随机化。本页没有、也不声称已经裁决 $P$ 对 $\mathrm{BPP}$。

第二层误解把 1978 年的 FOCS 与 1980 年的 STOC 焊成一次印刷，或听成阿德尔曼已经证明 $NP\subseteq\mathrm{P/poly}$。卡普与利普顿的引言把阿德尔曼写成已知的正向箭头：随机多项式时间接受的集合有小电路；他们要走相反的箭头，问 SAT 一旦也有小电路，均匀层次会付出什么。两句话共用 $\mathrm{P/poly}$ 这个后来才固定的记号，对象却一正一反。把「随机性可以被忠告替换」听成「可满足性已经有小电路」，会把一次对 $\mathrm{BPP}$ 的上界收成一次对 $NP$ 的上界。本页停在随机多项式时间。层次坍缩是邻居，见 卡普–利普顿，不是这九页的封面。

第三层误解把印刷里的随机多项式时间听成后世教材默认的双侧错误类 $\mathrm{BPP}$，或把吉尔 1977 年的定义论文焊进安阿伯的九页。阿德尔曼与曼德斯（Kenneth Manders）1977 年在 STOC 把类 $R$ 写成「随机多项式时间」：是实例上，独立抛硬币后以显著间隙接受；非实例上，任何硬币都不接受。后来通行的名字是 $\mathrm{RP}$。吉尔 1977 年刊于 SIAM Journal on Computing 第 6 卷第 4 期、页码 675 至 695 的《Computational complexity of probabilistic Turing machines》，把双侧有界错误写成 $\mathrm{BPP}$，会议先行本是 1974 年 STOC。安阿伯文本处理的是可以放大的随机多项式时间；课堂把同一套计数改写成双侧错误加多数票，并仍称阿德尔曼定理。本奈特与吉尔 1981 年在随机神谕论文里把 $\mathrm{BPP}\subseteq\mathrm{P/poly}$ 写清楚，那是后一篇，DOI 为 10.1137/0210008，不是把 1978 年再印一遍。把 $R$、$\mathrm{BPP}$ 与 $NP$ 焊在一句里，会把一次单侧存在性收成一次证人类。

第四层误解把西普塞尔–加奇–劳特曼、因帕利亚佐–维格德森、概率可验证明或公钥方案的拆解焊进页码 75 至 83。$\mathrm{BPP}$ 掉进多项式层次的第二层，是 1980 年代的量词论证，不是安阿伯的电路计数。硬度换随机性、伪随机发生器、自然证明，都不在这九页里。同年 RSA 只说明作者是同一个人，封面仍是随机多项式时间与电路。

放大、多数票，以及一条忠告怎样钉死所有等长输入#

装置从一台带硬币的多项式时间机器开始。1970 年代中期，素性检测与有限域上的多项式分解已经把「抛硬币」从修辞变成一类多项式时间手续：米勒 1975 年的 STOC 文本、伯利坎普 1970 年的分解算法，以及吉尔对概率图灵机的分类，都出现在安阿伯文本的书目里。本页不问怎样实现其中任何一条算法，只问这类手续一旦被当成复杂度类，成员资格能不能被确定性的小电路接住。

输入是串 $x$，长度为 $n$。机器另读一条随机串 $r$，在确定性多项式步内输出接受或拒绝。随机多项式时间要求：对每个 $x$，错误概率被一个与 $n$ 无关的常数封顶，严格小于二分之一。单侧版本里，非实例上错误是零：任何 $r$ 都不把「否」说成「是」。双侧版本里，是与否两边都允许小于三分之一的错误。这两种写法都允许同一件数学手续：独立再跑多项式多次。单侧用「有一次接受就接受」，把漏网压成指数小。双侧用多数票，切尔诺夫 1952 年的尾界保证：要把错误从常数压到 $2^{-(n+1)}$，重复次数只需 $n$ 的多项式。放大改变的是硬币串的长度，仍是多项式。本页只使用这条概率事实，不把重复写成产品里的轮数表。

固定长度 $n$。放大之后，对每一个具体的 $x$，使机器说错的硬币串 $r$ 至多占全部硬币空间的 $2^{-(n+1)}$。长度为 $n$ 的输入一共 $2^n$ 个。即便这些坏集合彼此不交，它们并起来仍装不满一半的硬币空间： \[ 2^n\cdot 2^{-(n+1)}=2^{-1}<1. \] 因此至少存在一条硬币串 $r_n$，对所有长度为 $n$ 的输入都诚实。这条串就是忠告 $\alpha_n$。确定性多项式时间机器读 $(x,\alpha_n)$，按原来的转移走完，不再抛硬币。长度为 $n$ 的成员资格于是被一条多项式长的字钉死。序列 $\{\alpha_n\}$ 本身不必可计算：允许「每个长度在数学上存在一条好硬币」，并不允许「有一台机器枚举所有长度上的好硬币」。

电路是同一句话的组合形态。把 $r_n$ 硬接到转移函数里，时序计算按萨维奇 1972 年的摊开变成一张布尔电路 $C_n$：规模被运行时间的多项式封顶，$C_n$ 在长度为 $n$ 的输入上输出成员资格。萨维奇原文刊于 Journal of the ACM 第 19 卷第 4 期，页码 660 至 674，处理的是确定性时间；阿德尔曼补上的是：随机性一旦被放大到可以并集，就可以先变成忠告，再进入同一套摊开。$\mathrm{P/poly}$ 于是有两种彼此翻译的写法。其一是多项式规模电路族。其二是多项式时间加多项式忠告。两种写法描述同一类。$P$ 住在这个类里，是萨维奇的方向；随机多项式时间掉进去，是阿德尔曼的方向。

单侧与双侧在计数上只差「怎样合并多次运行」。单侧的好硬币是一条对所有是实例都接受、对所有非实例都不接受的串；存在性来自并集，因为非实例上本来就没有坏硬币。双侧必须先用多数票把每个实例的坏硬币压短，再对 $2^n$ 个输入取并。课堂写 $\mathrm{BPP}$，是因为多数票把双侧收进同一条并集。印刷处理的随机多项式时间，是这条并集能够成立的那个类。无论哪一种写法，被钉死的都是该长度上的全部输入，不是某一个样本。把「存在 $r_n$」听成「随机抽一次就能用」，会把一次存在性计数收成一次抽样算法。并集界只说明坏集合装不满空间；它不指出哪一条是好的，也不给出均匀的搜索手续。

稀疏集是同一扇门的另一种金属。多项式长的忠告可以把每个长度上需要记住的例外列成一张表；图灵归约到稀疏神谕，与 $\mathrm{P/poly}$ 重合。阿德尔曼的箭头因此也可以读成：随机多项式时间图灵归约到某类稀疏集。本页不把这张表写成编码格式，也不把归约写成询问机的装配说明书。神谕随询问内容而变；忠告只随长度而变。贝克、吉尔与索洛维的神谕是另一套装置，见 一九七五年论文。把忠告听成「免费问任意问题的黑箱」，会把一次长度相关的字收成一座相对化世界。

它证明了什么，没有覆盖什么#

它证明了：可放大的随机多项式时间具有多项式规模电路族，也就是后来所写的 $\mathrm{BPP}\subseteq\mathrm{P/poly}$。印刷先处理随机多项式时间类 $R$；课堂把同一套放大加并集写到双侧错误上，结论形状不变。$\mathrm{P/poly}$ 等于多项式时间加多项式忠告，也等于多项式规模电路族。$P$ 已经住在这个类里；本页把带硬币的多项式时间也送进去。方法论上的句子是：错误率一旦低于输入个数的倒数，并集就会留下一条对整个 $\{0,1\}^n$ 都诚实的硬币。非均匀性吃掉的是这一条存在性，不是一台对所有 $n$ 通用的发生器。

它没有证明 $P=\mathrm{BPP}$，也没有证明 $P\neq\mathrm{BPP}$。均匀去随机化要求忠告本身可在确定性多项式时间内被造出来，或被一台伪随机发生器冒充。那是后年的硬度换随机性，不在页码 75 至 83 里。它没有证明 $NP\subseteq\mathrm{P/poly}$，也没有证明 $NP\subseteq\mathrm{BPP}$。若 SAT 进入 $\mathrm{BPP}$，本页会把它送进 $\mathrm{P/poly}$，再由卡普–利普顿逼出层次坍缩；那是两篇合读的条件句，不是 1978 年单独给出的定理。它没有把 $\mathrm{BPP}$ 放进多项式层次，也没有构造使 $\mathrm{BPP}$ 与 $P$ 相对化后分开或重合的神谕。它没有给出任何显式函数的超多项式电路下界，也没有打开常数深度。自然证明、代数化与概率可验证明同样不在。对照属于 电路复杂度 总览与 计算复杂性 地图。本页把「可放大的硬币怎样变成一条忠告」写成一次计数。概念证据到此为止。放大回答的是坏事件如何被指数压下去；并集回答的是为什么压下去之后空间里仍剩得下一条对所有等长输入都诚实的字。两句都不是操作单。

跨域连接#

• 电路复杂度：总览把 $\mathrm{P/poly}$ 画成「多项式门、深度不限、允许每个长度换一张图」的那一格。阿德尔曼证明随机多项式时间已经住在这一格：先放大、再并集、再把留下的硬币硬接进门。把后来的 $\mathrm{AC}^0$ 奇偶下界或自然证明提前读成本页，会把一次存在性上界收成一次门的塌缩。地图可以后写；本页只提供「随机性如何变成非均匀上界」的手续。
• 卡普–利普顿一九八〇年论文：两年后的条件句把箭头反过来。若 $NP$ 也掉进阿德尔曼送随机性进去的那个类，层次就停在第二层。两页合读才得到「SAT 大概没有高效随机算法」的压力：随机算法会被本页收成电路，电路会触发层次坍缩。本页单独只说随机性进得去；卡普–利普顿单独只说 $NP$ 进去会出事。把 1978 年听成已经排除 SAT 的随机算法，会把一次上界收成一次下界。
• 随机算法：算法页管蒙特卡洛、拉斯维加斯与误差放大在素数检测上的形状。本页把放大从工程可靠性改写成复杂度类的闭合性：一旦错误可被多项式次重复压到 $2^{-n}$ 以下，整个长度上的硬币空间就装得下一张确定性电路。它不是把米勒–拉宾的轮数表写成实现步骤，也不把「错误小于 $4^{-k}$」收成一次去随机化。
• 密码学基础：现代公钥体系里的对手被允许是非均匀的：每个安全参数可以预计算一份忠告，模型正好住在 $\mathrm{P/poly}$。本页说明随机多项式时间也在同一侧，因而「我有一个高效随机算法」并不能把问题移出非均匀对手能够计算的范围。单向函数与平均情况硬度是更强的假设，不在这九页里。本页不把忠告、电路或随机性写成拆解步骤，更不提供如何利用一条存在性硬币去攻一个系统。
• 概率：并集界与切尔诺夫尾界在这里不是抽样习题，而是一次把「几乎所有硬币对单个输入诚实」提升成「存在一条硬币对所有等长输入都诚实」的提升。概率论提供间隙；复杂性把间隙花在输入个数 $2^n$ 上。把存在性听成随机抽样一次即可，会把一次计数收成一次实验。
• 证明：非构造性存在把「什么样的上界算数」写成数学对象。一份只证明「每个长度存在电路」的论证，并不自动给出均匀算法；它给出的是忠告机与电路族之间的翻译权。被排除的不是证明的可能性，而是把非均匀存在与均匀可构造混为一谈的那一类跳跃。把「课堂相信 $P=\mathrm{BPP}$」听成「1978 年已经证明」，会把一次存在性上界收成一次已完成的去随机化。

参考文献#

• L. Adleman, "Two Theorems on Random Polynomial Time", Proceedings of the 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, 16–18 October 1978, pp. 75–83. DOI: 10.1109/SFCS.1978.37. —— 本文对象：随机多项式时间具有多项式规模电路；后世课堂写成 $\mathrm{BPP}\subseteq\mathrm{P/poly}$。
• John Gill, "Computational complexity of probabilistic Turing machines", SIAM Journal on Computing 6(4), 1977, pp. 675–695. DOI: 10.1137/0206049. —— 双侧有界错误类 $\mathrm{BPP}$ 的期刊定义；会议先行本为 1974 年 STOC。
• Leonard Adleman & Kenneth Manders, "Reducibility, randomness, and intractability", Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977, pp. 151–163. DOI: 10.1145/800105.803405. —— 随机多项式时间类 $R$ 的先行讨论，安阿伯文本所依。
• J. E. Savage, "Computational Work and Time on Finite Machines", Journal of the ACM 19(4), 1972, pp. 660–674. DOI: 10.1145/321707.321718. —— $P$ 中集合具有小电路；忠告被钉死后的摊开所依。
• Richard M. Karp & Richard J. Lipton, "Some Connections between Nonuniform and Uniform Complexity Classes", Proceedings of the 12th Annual ACM Symposium on Theory of Computing, Los Angeles, 28–30 April 1980, pp. 302–309. DOI: 10.1145/800141.804678. —— 反向箭头：若 $NP\subseteq\mathrm{P/poly}$ 则多项式层次坍缩；不是本页封面。
• T. Baker, J. Gill & R. Solovay, "Relativizations of the P =? NP Question", SIAM Journal on Computing 4(4), 1975, pp. 431–442. DOI: 10.1137/0204037. —— 相对化邻居：神谕与忠告不是同一种额外信息；刊于 SIAM，不是 JACM。
• C. H. Bennett & J. Gill, "Relative to a Random Oracle $P^A \neq NP^A \neq \mathrm{co}\text{-}NP^A$ with Probability 1", SIAM Journal on Computing 10(1), 1981, pp. 96–113. DOI: 10.1137/0210008. —— 后年把 $\mathrm{BPP}\subseteq\mathrm{P/poly}$ 写进随机神谕文本；不是 1978 年的第二印刷。
• Herman Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations", Annals of Mathematical Statistics 23(4), 1952, pp. 493–507. DOI: 10.1214/aoms/1177729330. —— 双侧放大所用的尾界。
• Gary L. Miller, "Riemann's Hypothesis and Tests for Primality", Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975, pp. 234–239. DOI: 10.1145/800116.803773. —— 安阿伯文本所引的素性检测先行本；本页只用它标明随机多项式时间的现场，不把检测写成步骤。
• E. R. Berlekamp, "Factoring Polynomials Over Large Finite Fields", Mathematics of Computation 24(111), 1970, pp. 713–735. DOI: 10.1090/S0025-5718-1970-0276200-X. —— 安阿伯文本所引的分解算法；同样只作现场，不是配方。

延伸阅读#

• 与 计算复杂性 对读：地图用一句话记下本页；本页把那句话还原成 FOCS 1978 页码 75 至 83。
• 与 电路复杂度 对读：总览管 $\mathrm{P/poly}$、浅电路与后来的下界；本页停在随机性进入这一格的手续。
• 与 卡普–利普顿一九八〇年论文 对读：正向箭头在本页，反向箭头在那八页。
• 与 随机算法 对读：算法页管放大在具体问题上的形状；本页管放大对复杂度类的闭合。
• 与 贝克–吉尔–索洛维一九七五年论文 对读：神谕随询问而变，忠告只随长度而变。
• 与 库克一九七一年论文 对读：完全性把整类送进假设；本页不把 SAT 送进 $\mathrm{P/poly}$。
• 与 C. Lautemann, "BPP and the Polynomial Hierarchy", Information Processing Letters 17, 1983, pp. 215–217 对读：后年把 $\mathrm{BPP}$ 放进 $\Sigma_2^{\mathrm{P}}\cap\Pi_2^{\mathrm{P}}$，不是安阿伯的电路计数。
• 与 Nisan–Wigderson 1994 对读：本页把可放大的随机性送进非均匀电路；那一篇把足够硬的函数做成生成器，去骗均匀的多项式测试。均匀 $P=\mathrm{BPP}$ 的指数硬度条件句见 Impagliazzo–Wigderson 1997。忠告替换不是硬度换随机性。