Toda 定理

存在量词问“有没有”，奇偶计数只知道“解数是奇还是偶”。随机哈希可以把任意非空解集隔离出一个元素，使奇偶位以正常数概率看见它。重复后再把各次结果的 OR 编码进一个奇偶计数，就能模拟存在量词；取补处理全称量词。固定层数保证反复构造仍只有多项式规模。

随后要去掉随机性。直接加总各种子的原始计数没有用，因为偶数计数也会贡献大量数值。核心提升多项式先把每个偶数送到高次模数下的零，把每个奇数送到同一模数下的一。再加总并取余，读到的就恰好是接受种子的数量。

四个随机种子的模提升 ​

设随机种子长 $r=2$，四个种子的计数依次为 $2,1,3,1$。其中三个为奇数，接受概率为 $3/4$。令

两次迭代得到：

提升后的计数之和满足

因为真实接受数在 $[0,4]$，模8的标准余数唯一确定它。第一轮出现负数并非错误；这正是先使用 GapP，再拆成两个 #P 函数查询的原因。

一份有偶数个解的实例不能只问一次奇偶 ​

例如解集 $S=\{00,11\}$ 有两个元素，直接奇偶查询返回零，却并非空集。若取仿射约束 $h(z)=z_1=0$，只留下 $00$，奇偶查询就返回一。归约不知道解集，不能有意挑这个约束；下面证明随机仿射哈希对每个非空集合都有统一的隔离概率。

若某一步需要给计数器增加一个自由变量，该变量会让每个见证重复两次，改变奇偶值。因此所有算术构造都必须说明标签分支和无用位如何唯一补齐。普通“有解当且仅当有解”的归约不足以替代这里的保计数构造。

奇偶计数的算术接口 ​

若 $A,B\in \mathrm{\#}\mathrm{P}$，则 $A+B$ 和 $AB$ 也在 #P。加法先选标签，再验证相应见证，另一个分支未使用的位置唯一补零；乘法独立猜两份见证并同时验证，接受数是笛卡尔积大小。多项式多个因子的乘积同理；不能重复使用同一份见证后仍声称计数相乘。

常数一由唯一见证实现。因此 $1+A$ 的奇偶是 $A$ 奇偶的补，且对任意多项式多个 $A_j$，

若全为偶数，乘积为奇数，加一后为偶数；若至少一项为奇数，乘积为偶数，加一后为奇数。把乘积换成和只会得到 XOR，不能用于 OR 型成功放大。

对多项式长度的 $z$，$\sum _{z}A(x,z)$ 也在 #P：先猜 $z$，再猜并验证相应见证。求和包含指数多个 $z$，但每条验证路径只处理一个，仍是多项式时间。这些闭包都在描述隐式计数器，没有真的枚举其全部分支。

哈希隔离：对任意非空集合的统一界 ​

设非空 $S\subseteq \{0,1{\}}^m$，$m\ge 1$。随机选择二元矩阵 $A\in {\mathbb{F}}_2^{k\times m}$ 和向量 $b\in {\mathbb{F}}_2^k$，令 $h(z)=Az+b$，所有条目独立公平。

对固定 $z$，$h(z)$ 均匀；对 $z\ne w$，每行的两值 $a\cdot z+b$ 与 $a\cdot w+b$ 是两个线性独立约束，故均匀且独立。各行又独立，因此

令 $N=|S\cap h^{-1}(0)|$、$s=|S|$。逐整数检查有 $N-N(N-1)\le {\mathbf{1}}_{\{N=1\}}$，所以

总能在 $k=2,\dots ,m+1$ 中找到一个使 $2^{k-2}\le s\le 2^{k-1}$ 的值。此时 $\lambda =s/2^k\in [1/4,1/2]$，故隔离概率至少 $\lambda -{\lambda }^2\ge 3/16\ge 1/8$。空集则在所有哈希下仍为空。这是 Valiant–Vazirani 隔离思路的具体仿射版本；它不需要事先计算或列出 $S$。[2]

为了只使用有固定长度的公平随机串，我们不从非二次幂范围随机抽 $k$。每一轮对全部 $k=2,\dots ,m+1$ 分别独立选一份哈希；其中至少一份有上述保证。独立进行

轮，把所有哈希下的奇偶结果做 OR。若集合非空，全部失败的概率至多

所用哈希共有 $mT$ 份，其描述长度与生成时间都是 $m,b$ 的多项式。

固定层数的量词如何逐层消去 ​

证明更精确的归纳断言：对任意固定量词块数 $c$、固定 PH 谓词 $\beta (x)$ 和整数精度 $b\ge 1$，可以在 ${\mathrm{poly}}_c(|x|,b)$ 时间内描述 #P 计数器 $F(x,s)$，种子和见证长度也受这个多项式控制，且

对每个固定 $x$ 成立。精度作为一元参数处理；不是声称关于 $\log b$ 的多项式界。

没有量词时，确定性验证谓词直接产生零或一个接受见证。若外层是 $\mathrm{\exists }z\gamma (x,z)$，把 $z$ 写成固定多项式长度 $m\ge 1$ 的比特串。空块可删掉。对内层用精度 $b+m+2$ 的归纳构造，得到 $F_s(x,z)$。对固定 $x$，让所有 $z$ 使用同一份种子 $s$，并合界给出

这里仅声称对一个固定 $x$，其全部 $z$ 同时正确；不把逐输入概率擅自换成一份种子对全部输入都正确。

在这件好事发生时，$F_s(x,z)$ 的奇偶恰描述真实集合 $S_x=\{z:\gamma (x,z)=1\}$。再独立抽上一节的哈希，定义

这是 #P 计数器：先猜 $z$ 并检查哈希，再运行内层验证器。其奇偶等于哈希选中真实集合的元素数之奇偶。即使 $\gamma$ 本身带有量词，也没有被当成可直接计算的判定子程序；实际运行的是内层 #P 验证器。

将全部 $A_h$ 按 $1+\prod _h(1+A_h)$ 合成一个计数器。条件在内层全部正确时，外层隔离失败概率至多 $2^{-(b+2)}$；不条件化的总错误因而至多

对全称块使用 $\mathrm{\forall }z\gamma =\mathrm{\neg }\mathrm{\exists }z\mathrm{\neg }\gamma$，奇偶取补由计数加一实现，双侧错误率不变。每层只把描述、见证和随机串长度增大一个多项式因子，层数 $c$ 固定，故全部构造仍是多项式。取 $b=2$ 已有错误至多 $1/4<1/3$，从而证明 $\mathrm{PH}\subseteq \mathrm{BP}\cdot \oplus \mathrm{P}$。[2]

这个归纳不承诺某一侧零错误。若把内层偶数个真分支中的一个漏掉，奇偶可能从零变一；双侧误差和显式并合界正好处理这件事。

核心提升引理：模数指数每次翻倍 ​

GapP 除了上述和与积，还允许相减。可把它理解为正、负两类见证的数量差：加法用带符号的标签分支，取负交换符号，乘法猜两份见证并把符号相乘。正贡献和负贡献各自由一个 #P 验证器计数。[1]

对任意整数 $a$、$j\ge 1$ 和 $ϵ\in \{0,1\}$，有

若 $a\equiv 0$，由 $q(a)=a^2(3-2a)$ 立刻成立。若 $a=1+t$、$2^j\mid t$，直接展开

对负整数同样成立。迭代 $k$ 次后，模数从 $2$ 提高到 $2^{2^k}$，奇偶位始终作为零或一保留。[1, Lemma4.4]

若原种子长 $r=r(|x|)$，取 $k=\lceil {\log }_2(r+1)\rceil$，令

因为 $2^k\ge r+1$，可得

$H$ 仍在 GapP，但需要核算规模：每次表达式替换为 $3a^2-2a^3$，完全展开只增加常数倍的子表达式副本；$k=O(\log (r+1))$ 次后只有 $\mathrm{poly}(r+1)$ 个副本，而不是指数于 $r$。所有系数可由常数个标签分支表示；见证长度、验证时间和计数答案的二进制位长均保持多项式。$r=0$ 时 $k=0$，无须提升。

两次精确计数如何恢复接受种子数 ​

构造

外层机器不会枚举所有种子；两个计数器各先猜 $s$，再运行正或负贡献验证器。查询 $U(x),V(x)$ 后，用多项式位长的整数运算计算标准非负余数

设真正的奇数种子数为 $a(x)$。逐种子提升表明 $G(x)\equiv a(x)(\mathrm{mod}{2}^{r+1})$，而 $0\le a(x)\le 2^r<2^{r+1}$，故余数恰等于 $a(x)$。即使 $G(x)$ 为负，也要取这个标准余数，不能直接用编程语言中可能为负的余数表示。

最后比较 $2A(x)>2^r$。是实例的比例至少 $2/3$，否实例至多 $1/3$，因此严格多数可靠地区分二者；此写法也覆盖 $r=0$。两函数可用标签合并成一个固定 #P oracle，或各自保计数归约到 #SAT。外层全过程确定性且多项式，定理得证。

结论的范围 ​

定理给出精确计数对固定量词层级的统摄力，不给出普通多项式算法。若所有 #P 函数都在 FP 中，则本定理推出 PH=P；定理本身没有假设这一点，也没有证明 PH 坍缩。

PP公理库复杂度类 PPPP · Probabilistic polynomial time由概率多项式时间机器以严格多数计算路径判定的语言集合。研究计数是否超过阈值。精确 #P 值可通过多项式次阈值查询和二分恢复，所以 $P^{\mathrm{\#}P}=P^{PP}$；反向则直接用精确计数回答每个阈值。这个等式仍在带 oracle 的 P层面，不能删除外面的 P，声称本文证明了 $PH\subseteq PP$。

固定交替层数是规模论证的前提。层数随输入增长时，反复多项式膨胀未必仍是多项式，因而这份证明不把 PSPACE 或一般 TQBF 纳入同一结论。近似计数也不足以直接计算高次模数下的标准余数，不能替换正文的精确接口。