[科普中国]-户田定理

户田定理是理论计算机科学的复杂度理论的重要结果，它指出在多项式谱系和计数问题之间的内在联系。

定义根据户田定理，多项式谱系内的所有问题均可以在多项式时间内归约为求解多项式个（实际上可以规约为1个）“求令给定布尔表达式为真的可能赋值的数量”（#SAT）问题（参见：布尔可满足性问题）。户田定理的证明由户田诚之助（英语：SeinosukeToda）在1991年给出，并在1998年为证明者赢得了当年的哥德尔奖。（在1991年的该篇论文中，户田诚之助实际上证明了（参见：PP），而上述结果是这个结果的一个自然推论。）
户田定理的证明主要包含以下两部分：
一个概率性的证明指出；
通过去随机化过程证明上述复杂度类在P#P内。1

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

去随机化证明的第二部分（去随机化）将每个的实例映射到一个问题。具体而言，去随机化过程将每个问题的实例映射到另一个布尔表达式，其真赋值个数（用表示）模一个大数余；另一方面，每个不属于的布尔表达式则被映射到一个表达式，其真赋值个数模同一个大数余。
这样，给定一个多项式谱系内的实例，我们可以求以下表达式：
在本身为真的时候，大多数（例如，多于3/4）的实例会返回的实例，因此会得到(模）；同理，在为假的时候，大多数的会得到。因此，在求模的大数足够大时，这两个情况（为真和为假）所对应的的取值区间是不重合的。如果我们能求解，则我们可以立即判定任何多项式谱系内的是否为真。
但是，注意到上述的表达式的子项数事实上达到了指数级（因为的长度可以是输入长度的多项式），因此直接求和是不可行的。
一个解决方法是注意到实际上是一个SAT表达式，因此可以考虑下面的SAT问题：“求使得为真”。注意的真赋值个数等于。因此，如果我们能在多项式时间内求解一个#SAT问题（也就），我们就可以判定，所以是的一个子集。2

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学