戸田の定理のソースを表示

'''戸田の定理'''(とだのていり、[[英語|英]]: '''Toda's theorem''')とは、1991年に[[戸田誠之助]]が証明した[[計算量理論]]における定理である<ref>{{Cite journal|last=Toda|first=Seinosuke|date=1991-10|title=PP is as Hard as the Polynomial-Time Hierarchy|url=http://epubs.siam.org/doi/10.1137/0220053|journal=SIAM Journal on Computing|volume=20|issue=5|pages=865–877|language=en|doi=10.1137/0220053|issn=0097-5397}}</ref>。戸田はこの功績により1998年の[[ゲーデル賞]]を受賞している。

== 主張 ==
この定理は多項式階層にあるすべてのクラスの和集合である[[PH (計算複雑性理論)|PH]]がP<sup>PP</sup>に含まれることを示している。また、この事実よりPHがP<sup>#P</sup>に含まれていることも示される。

== 定義 ==
[[＃P|#P]]は多項式時間で検証可能な問題(つまりは[[NP]]に属する問題)に対する解の数を正確に数える問題の集合であり、[[PP (計算複雑性理論)|PP]] は、間違う確率が常に1/2未満となるような[[確率的チューリング機械]]で[[多項式時間]]で解ける[[決定問題]]の集合である。P<sup>#P</sup>は，#Pの任意の(#P[[神託機械#神託機械の複雑性クラス|オラクル]]に対して多項式時間)に対する答えを瞬時に得ることができれば、多項式時間で解くことができるすべての問題から構成される。従って、戸田の定理より、多項式階層の任意の問題に対して[[数え上げ問題]]<sub>([[:en:Counting_problem_(complexity)|英語版]])</sub>への決定性[[多項式時間変換]]が存在することが意味される。<ref>[http://sigact.acm.org/Prizes/Godel/1998.html 1998 Gödel Prize. Seinosuke Toda]</ref>

[[BSS機械]]<sub>([[:en:Blum-Shub-Smale_machine|英語版]])</sub>に基づく実数上の複雑性理論での類似の結果は、2009年にSaugata BasuとThierry Zellによって証明され<ref name="basu09">Saugata Basu and Thierry Zell (2009); [http://www.math.purdue.edu/~sbasu/toda16.pdf ''Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem''], in ''Foundations of Computational Mathematics''</ref>、2011年にはSaugata Basuによって戸田の定理の複素数類似が証明された。<ref name="basu11">Saugata Basu (2011); [http://www.math.purdue.edu/~sbasu/focm_final-09-20-11.pdf ''A Complex Analogue of Toda's Theorem''], in ''Foundations of Computational Mathematics''</ref>

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

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

:: <math>\Sigma^P \cdot \mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P}</math>

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

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

:: <math>\mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{P}^{\sharp P}</math>

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

: <math>\mathsf{PH} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{P} \cdot \oplus \mathsf{P} \subseteq \mathsf{P}^{\sharp P}</math>

== 参考文献 ==
{{reflist}}

{{DEFAULTSORT:とたのていり}}
[[Category:計算複雑性理論の定理]]
[[Category:数学に関する記事]]