戸田の定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/08/17 10:20 UTC 版)
戸田の定理(とだのていり、英: Toda's theorem)とは、1991年に戸田誠之助が証明した計算量理論における定理である[1]。戸田はこの功績により1998年のゲーデル賞を受賞している。
主張
この定理は多項式階層にあるすべてのクラスの和集合であるPHがPPPに含まれることを示している。また、この事実よりPHがP#Pに含まれていることも示される。
定義
#Pは多項式時間で検証可能な問題(つまりはNPに属する問題)に対する解の数を正確に数える問題の集合であり、PP は、間違う確率が常に1/2未満となるような確率的チューリング機械で多項式時間で解ける決定問題の集合である。P#Pは，#Pの任意の(#Pオラクルに対して多項式時間)に対する答えを瞬時に得ることができれば、多項式時間で解くことができるすべての問題から構成される。従って、戸田の定理より、多項式階層の任意の問題に対して数え上げ問題(英語版)への決定性多項式時間変換が存在することが意味される。[2]
BSS機械(英語版)に基づく実数上の複雑性理論での類似の結果は、2009年にSaugata BasuとThierry Zellによって証明され[3]、2011年にはSaugata Basuによって戸田の定理の複素数類似が証明された。[4]
証明
証明は大きく二つの部分から成る。
- 第一に、以下が成り立つ。
- 戸田の定理のページへのリンク
