
_START_ARTICLE_
戶田定理
_START_SECTION_
P
        H
        ⊆
        B
        P
        
          P
          
            ⊕
            P
          
        
      
    
    {\displaystyle PH\subseteq BPP^{\oplus P}}
_START_PARAGRAPH_
第一部分的证明基于瓦里安特-瓦兹拉尼定理。该定理指出如果唯一SAT(Unique-SAT，或USAT)问题（亦即，仅在一个布尔表达式没有令其为真的赋值，和在有一个唯一的赋值之间做出判定，而对于有一个以上真赋值的布尔表达式可做任何输出）有一个多项式的随机化算法，则（参见：RP (复杂度)）。事实上，该定理给出了这样一个判定USAT问题的随机算法。_NEWLINE_虽然我们尚不知如何提高Unique-SAT问题的随机算法的准确性，但对于USAT问题的Parity（奇偶性）版本（亦即，将前述问题中的“唯一赋值”改为“奇数个赋值”），我们可以通过重复执行随机算法以提高算法准确性。由此，我们可以通过对多项式谱系的深度采用数学归纳法，得到一个的证明（参见：BPP）。注意这个证明实际上给出一个映射（对于每个随机数取值，存在一个映射），将每个值为真的多项式谱系实例映射到一个的实例（亦即，一个有着奇数个真赋值的布尔表达式），而将每个非真的实例映射到一个有偶数个（不一定为0个）真赋值的布尔表达式。