$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem
Lance Fortnow
cs.CC
2026-09-28
Fortnow用指数相关界构造多项式种子PRG，证明Almost-⊕P=BP·⊕P，并完成Toda前半的随机预言机证明。
复杂度理论里有一条和 BPP 平行的问题:一个语言若对几乎所有预言机都落进某个类,它是否已经落进对应的有界误差类。Bennett 和 Gill 给出 Almost-P = BPP。Nisan 和 Wigderson 给出 Almost-PH = PH。奇偶计数这一侧一直空着。
⊕P 是 NP 的奇偶版本,接受条件是非确定性机器的接受路径条数为奇数。Almost-⊕P 要求对随机预言机 R 以概率 1 落在 ⊕P^R 里。BP·⊕P 是对 ⊕P 做有界误差随机归约后的类。要对齐的就是这两边。
Toda 定理前半是 PH ⊆ BP·⊕P,整个多项式层级都能随机归约到一次奇偶计数。Regan 和 Royer 曾想先在随机预言机下把 PH 一层层压进 ⊕P,再拿掉预言机。摘要说这条路此前没走完。能看到的缺口是一个伪随机发生器:种子多项式长,却要骗过指数个变量上、次数仍是多项式的 F₂ 多项式。没有它,随机预言机上的奇偶计算收不回短随机性。
Fortnow 用的是 Chattopadhyay、Hatami、Lee、Lovett、Tal 和 Viola 的指数相关界。一边是 F₂ 上的多项式,另一边是多数函数的 XOR,两者相关性指数小,低次多项式几乎分不出后者和随机串。做成发生器,就是用短种子扩成长串,让多项式次的 F₂ 多项式骗不过去。
摘要只给定性参数:种子多项式长,变量数可到指数,次数保持多项式。随机预言机相当于一张指数大的真值表。⊕P 机器只能做多项式次查询,但要模拟「对随机预言机概率 1 成立」,发生器必须在指数多个坐标上同时骗过低次多项式。种子却必须是多项式长,否则放不进 BP 算子。⊕P 相对随机预言机的查询往往能写成这类多项式。发生器把预言机换成短种子,剩余随机性进 BP 算子,Almost-⊕P 落到 BP·⊕P。反向包含在 Almost 结果里通常跟定义走,摘要没单写。
Toda 前半走 Regan 和 Royer 的路线。相对随机预言机,每一层先做 Valiant-Vazirani,把 SAT 随机打成至多一个解,等于拆开 NP 量词;再调用 Papadimitriou-Zachos 的塌缩 ⊕P^⊕P = ⊕P。一层层做,PH 在随机预言机下进 ⊕P,全程没有概率量词被移过预言机。得到 PH ⊆ Almost-⊕P。接上主定理,预言机消失,变成无预言机的 PH ⊆ BP·⊕P。
摘要会把这条论证对照 Fortnow 2009 年的 Toda 简证。对照细节在未取到的原文里。
纯证明论文,摘要没有实验数字,也没有种子次数或误差的定量式。
| 结论 | 内容 | 对照 |
| 主定理 | Almost-⊕P = BP·⊕P | Bennett-Gill 的 Almost-P = BPP; Nisan-Wigderson 的 Almost-PH = PH |
| 关键工具 | 多项式种子 PRG,骗多项式次、指数变量的 F₂ 多项式 | 相关界来自 Chattopadhyay 等人 |
| Toda 前半 | PH ⊆ BP·⊕P | 随机预言机上先塌进 ⊕P,再去掉预言机 |
| 证明约束 | 从不把概率量词移过预言机 | 与常见相对化写法的差别 |
种子的具体次数、相关界的指数底、PRG 误差如何传递,摘要都没给,只能去原文核对。
对做复杂度、去随机化和计数层级的人,这是 Almost 纲领在 ⊕P 上的缺页。Toda 的结论不新。新的是路径:先相对随机预言机一层层塌,再用 F₂ 多项式 PRG 拿掉预言机,全程不让 BP 量词钻进预言机查询。
它变不成可跑的算法,也不改训练或推理栈。已经在读 Toda 归约、Valiant-Vazirani isolation 或 F₂ 多项式伪随机的人,可以把「相关界到 PRG 再到去掉随机预言机」看成一条接完的链。其他人仍可走 2009 年那份更短的简证。摘要把两条证明放在一起比,卖点是结构,不是长度。
全文未取到。种子是 n 的几次方、相关界的指数底、PRG 误差、对多项式次数的限制,都无法核对。Toda 后半 BP·⊕P ⊆ P^{#P} 这篇只做前半。
摘要写 complete a random-oracle proof,意味着 Regan-Royer 路线差的就是去预言机。差哪条引理没说。新证法有没有用到比 2009 简证更强的电路下界假设,也只能等原文。相关界被当黑盒。若那条界对次数或变量数的依赖不够均匀,这里的 PRG 可能只在某个多项式窗口里成立,摘要没给窗口。