戸田の定理

戸田の定理(とだのていり、英: Toda's theorem)とは、1991年に戸田誠之助が証明した計算量理論における定理である。戸田はこの功績により1998年のゲーデル賞を受賞している。

 主張 
この定理は多項式階層にあるすべてのクラスの和集合であるPHがPPPに含まれることを示している。また、この事実よりPHがP#Pに含まれていることも示される。

 定義 
#Pは多項式時間で検証可能な問題(つまりはNPに属する問題)に対する解の数を正確に数える問題の集合であり、PP は、間違う確率が常に1/2未満となるような確率的チューリング機械で多項式時間で解ける決定問題の集合である。P#Pは，#Pの任意の(#Pオラクルに対して多項式時間)に対する答えを瞬時に得ることができれば、多項式時間で解くことができるすべての問題から構成される。従って、戸田の定理より、多項式階層の任意の問題に対して数え上げ問題(英語版)への決定性多項式時間変換が存在することが意味される。1998 Gödel Prize. Seinosuke Toda

BSS機械(英語版)に基づく実数上の複雑性理論での類似の結果は、2009年にSaugata BasuとThierry Zellによって証明されSaugata Basu and Thierry Zell (2009); Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem, in Foundations of Computational Mathematics、2011年にはSaugata Basuによって戸田の定理の複素数類似が証明された。Saugata Basu (2011); A Complex Analogue of Toda's Theorem, in Foundations of Computational Mathematics

 証明 
証明は大きく二つの部分から成る。

 第一に、以下が成り立つ。



 証明では Valiant-Vaziraniの定理 (英語版）が用いられる。  が  を含み、補集合に関して閉じているため、帰納的に が導かれる。

 次に、以下が成り立つ。



この二つの結果より、以下の関係が導かれる。



 参考文献 

Category:計算複雑性理論の定理
Category:数学に関する記事