户田定理

第一部分的证明基于瓦里安特-瓦兹拉尼定理（英语：Valiant-Vazirani theorem）。该定理指出如果唯一SAT(Unique-SAT，或USAT)问题（亦即，仅在一个布尔表达式没有令其为真的赋值，和在有一个唯一的赋值之间做出判定，而对于有一个以上真赋值的布尔表达式可做任何输出）有一个多项式的随机化算法，则${\displaystyle NP=RP}$ （参见：RP (复杂度)）。事实上，该定理给出了这样一个判定USAT问题的随机算法。

虽然我们尚不知如何提高Unique-SAT问题的随机算法的准确性，但对于USAT问题的Parity（奇偶性）版本${\displaystyle \oplus SAT}$ （亦即，将前述问题中的“唯一赋值”改为“奇数个赋值”），我们可以通过重复执行随机算法以提高算法准确性。由此，我们可以通过对多项式谱系的深度采用数学归纳法，得到一个${\displaystyle PH\subseteq BPP^{\oplus P}}$ 的证明（参见：BPP）。注意这个证明实际上给出一个映射${\displaystyle F_{r}}$ （对于每个随机数取值${\displaystyle r}$ ，存在一个映射${\displaystyle F_{r}}$ ），将每个值为真的多项式谱系实例${\displaystyle \phi }$ 映射到一个${\displaystyle \oplus SAT}$ 的实例${\displaystyle F_{r}(\phi )}$ （亦即，一个有着奇数个真赋值的布尔表达式），而将每个非真的实例映射到一个有偶数个（不一定为0个）真赋值的布尔表达式。

证明的第二部分（去随机化）将每个${\displaystyle BPP^{\oplus P}}$ 的实例映射到一个${\displaystyle \#SAT}$ 问题。具体而言，去随机化过程${\displaystyle T}$ 将每个${\displaystyle \oplus SAT}$ 问题的实例${\displaystyle \psi }$ 映射到另一个布尔表达式${\displaystyle T(\psi )}$ ，其真赋值个数（用${\displaystyle \#T(\psi )}$ 表示）模一个大数${\displaystyle R}$ 余${\displaystyle -1}$ ；另一方面，每个不属于${\displaystyle \oplus SAT}$ 的布尔表达式${\displaystyle \psi '}$ 则被映射到一个表达式${\displaystyle T(\psi ')}$ ，其真赋值个数${\displaystyle \#T(\psi ')}$ 模同一个大数${\displaystyle R}$ 余${\displaystyle 0}$ 。

这样，给定一个多项式谱系内的实例${\displaystyle \phi }$ ，我们可以求以下表达式：

${\displaystyle S(\phi )=\displaystyle \sum _{r}\#T(F_{r}(\phi )).}$ 

在${\displaystyle \phi }$ 本身为真的时候，大多数（例如，多于3/4）的${\displaystyle F_{r}}$ 实例会返回${\displaystyle \oplus SAT}$ 的实例，因此${\displaystyle \#T(F_{r}(\phi ))}$ 会得到${\displaystyle -1}$  (模${\displaystyle R}$ ）；同理，在${\displaystyle \phi }$ 为假的时候，大多数的${\displaystyle \#T(F_{r}(\phi ))}$ 会得到${\displaystyle 0}$ 。因此，在求模的大数${\displaystyle R}$ 足够大时，这两个情况（${\displaystyle \phi }$ 为真和为假）所对应的${\displaystyle S(\phi )}$ 的取值区间是不重合的。如果我们能求解${\displaystyle S(\phi )}$ ，则我们可以立即判定任何多项式谱系内的${\displaystyle \phi }$ 是否为真。

但是，注意到上述${\displaystyle S}$ 的表达式的子项数事实上达到了指数级（因为${\displaystyle r}$ 的长度可以是输入长度的多项式），因此直接求和是不可行的。

一个解决方法是注意到${\displaystyle T(F_{r}(\phi ))}$ 实际上是一个SAT表达式，因此可以考虑下面的SAT问题${\displaystyle Q(\phi )}$ ：“求${\displaystyle (r,x)}$ 使得${\displaystyle T(F_{r}(\phi ))(x)}$ 为真”。注意${\displaystyle Q(\phi )}$ 的真赋值个数等于${\displaystyle S(\phi )}$ 。因此，如果我们能在多项式时间内求解一个#SAT问题（也就${\displaystyle \#Q(\phi )}$ ），我们就可以判定${\displaystyle \phi }$ ，所以${\displaystyle PH}$ 是${\displaystyle P^{\#P}}$ 的一个子集。