戸田の定理

戸田の定理は計算複雑性理論における結果であり、戸田誠之助が論文「PPは多項式時間階層と同じくらい難しい」^[1]で証明し、1998年のゲーデル賞を受賞した。

定理は、多項式階層 PH全体が P ^{PPに含まれていることを述べています。これは、 PH が P #P}に含まれているという密接に関連した記述を意味します。

#P は多項式的に検証可能な問題（つまり、NPの質問）に対する解の数を正確に数える問題であり、大まかに言えば、PP は半分以上の確率で正しい答えを出す問題です。クラス P ^#Pは、# P の任意の計数問題に対する瞬時の答えにアクセスできる場合に多項式時間で解決できるすべての問題で構成されます（#Pオラクルに対する多項式時間）。したがって、戸田の定理は、多項式階層の任意の問題に対して、計数問題への決定論的な多項式時間のチューリング還元が存在することを意味しています。^[2]

実数上の計算量理論における類似の結果（ブルーム・シューブ・スメール実チューリングマシンの意味で）は、2009年にサウガタ・バスとティエリー・ゼルによって証明されました^[3]。また、戸田の定理の複雑な類似は、2011年にサウガタ・バスによって証明されました^[4]。

証明は2つの部分に分かれています。

• まず、

${\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}}$

これら2つの部分を合わせると

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