戸田の定理

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

主張

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

定義

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

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

証明

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

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

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

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

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

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

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

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