戶田定理 在理論計算機科學的複雜度理論這一分支中戶田定理是一個重要的結果它指出在多項式譜系和計數問題英语Counting problem complexity之間的內在聯繫 P H  P  P  displaystyle PHsubseteq PP 根據戶田定理多項式譜系內的所有問題均可以在多項式時間內歸約為求解多項式個實際上可以規約為個求令給定布爾表達式為真的可能賦值的數量SAT問題參見布尔可满足性问题戶田定理的証明由戶田誠之助英语Seinosuke Toda在年給出並在年為証明者贏得了當年的哥德爾獎在年的該篇論文中戶田誠之助實際上證明了 P H  P P P displaystyle PHsubseteq PPP 參見PP而上述結果是這個結果的一個自然推論 戶田定理的証明主要包含以下兩部分 一個概率性的証明指出 P H  B P P  P displaystyle PHsubseteq BPPoplus P  通過去隨機化過程証明上述復雜度類在 P  P displaystyle PP 內