戸田の定理

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

主張

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

定義

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

BSS機械_(英語版)に基づく実数上の複雑性理論での類似の結果は、2009年にSaugata BasuとThierry Zellによって証明され^[3]、2011年にはSaugata Basuによって戸田の定理の複素数類似が証明された。^[4]

証明

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

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

${\displaystyle \Sigma ^{P}\cdot {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$

証明では Valiant-Vaziraniの定理 (英語版）が用いられる。 ${\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$ が ${\displaystyle {\mathsf {P}}}$ を含み、補集合に関して閉じているため、帰納的に ${\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$が導かれる。

• 次に、以下が成り立つ。

${\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\sharp P}}$

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

${\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\sharp P}}$

参考文献

1. Toda, Seinosuke (1991-10). “PP is as Hard as the Polynomial-Time Hierarchy” (英語). SIAM Journal on Computing 20 (5): 865–877. doi:10.1137/0220053. ISSN 0097-5397. http://epubs.siam.org/doi/10.1137/0220053.
2. 1998 Gödel Prize. Seinosuke Toda
3. Saugata Basu and Thierry Zell (2009); Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem, in Foundations of Computational Mathematics
4. Saugata Basu (2011); A Complex Analogue of Toda's Theorem, in Foundations of Computational Mathematics