在理论计算机科学复杂度理论这一分支中,户田定理是一个重要的结果,它指出在多项式谱系计数问题英语Counting problem (complexity)之间的内在联系:

根据户田定理,多项式谱系内的所有问题均可以在多项式时间归约为求解多项式个(实际上可以规约为1个)“求令给定布尔表达式为真的可能赋值的数量”(#SAT)问题(参见:布尔可满足性问题)。户田定理的证明由户田诚之助英语Seinosuke Toda在1991年给出,并在1998年为证明者赢得了当年的哥德尔奖[1]。(在1991年的该篇论文[2]中,户田诚之助实际上证明了(参见:PP),而上述结果是这个结果的一个自然推论。)

户田定理的证明主要包含以下两部分:

  • 一个概率性的证明指出
  • 通过去随机化过程证明上述复杂度类在内。

编辑

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

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

去随机化

编辑

证明的第二部分(去随机化)将每个 的实例映射到一个 问题。具体而言,去随机化过程 将每个 问题的实例 映射到另一个布尔表达式 ,其真赋值个数(用 表示)一个大数  ;另一方面,每个不属于 的布尔表达式 则被映射到一个表达式 ,其真赋值个数 模同一个大数  

这样,给定一个多项式谱系内的实例 ,我们可以求以下表达式:

 

 本身为真的时候,大多数(例如,多于3/4)的 实例会返回 的实例,因此 会得到  (模 );同理,在 为假的时候,大多数的 会得到 。因此,在求模的大数 足够大时,这两个情况( 为真和为假)所对应的 的取值区间是不重合的。如果我们能求解 ,则我们可以立即判定任何多项式谱系内的 是否为真。

但是,注意到上述 的表达式的子项数事实上达到了指数级(因为 的长度可以是输入长度的多项式),因此直接求和是不可行的。

一个解决方法是注意到 实际上是一个SAT表达式,因此可以考虑下面的SAT问题 :“求 使得 为真”。注意 的真赋值个数等于 。因此,如果我们能在多项式时间内求解一个#SAT问题(也就 ),我们就可以判定 ,所以  的一个子集。

参考资料

编辑
  1. ^ 1998 Gödel Prize. Seinosuke Toda. [2012-12-09]. (原始内容存档于2010-03-16). 
  2. ^ Toda, Seinosuke, PP is as hard as the polynomial-time hierarchy (PDF), SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics), 1991, 20 (5): 865–877 [2012-12-09], ISSN 1095-7111, doi:10.1137/0220053, (原始内容存档 (PDF)于2016-03-03)