戶田定理

在理論計算機科學的複雜度理論這一分支中，戶田定理是一個重要的結果，它指出在多項式譜系和計數問題（英语：Counting problem (complexity)）之間的內在聯繫：

${\displaystyle PH\subseteq P^{\#P}.}$

根據戶田定理，多項式譜系內的所有問題均可以在多項式時間內歸約為求解多項式個（實際上可以規約為1個）“求令給定布爾表達式為真的可能賦值的數量”（#SAT）問題（參見：布尔可满足性问题）。戶田定理的証明由戶田誠之助（英语：Seinosuke Toda）在1991年給出，並在1998年為証明者贏得了當年的哥德爾獎^[1]。（在1991年的該篇論文^[2]中，戶田誠之助實際上證明了${\displaystyle PH\subseteq P^{PP}}$（參見：PP），而上述結果是這個結果的一個自然推論。）

戶田定理的証明主要包含以下兩部分：

• 一個概率性的証明指出${\displaystyle PH\subseteq BPP^{\oplus P}}$；
• 通過去隨機化過程証明上述復雜度類在${\displaystyle P^{\#P}}$內。

${\displaystyle PH\subseteq BPP^{\oplus P}}$

第一部分的證明基於瓦里安特-瓦兹拉尼定理（英语：Valiant-Vazirani theorem）。該定理指出如果唯一SAT(Unique-SAT，或USAT)問題（亦即，僅在一個布爾表達式沒有令其為真的賦值，和在有一個唯一的賦值之間做出判定，而對於有一個以上真賦值的布爾表達式可做任何輸出）有一個多項式的隨機化算法，則${\displaystyle NP=RP}$ （參見：RP (複雜度)）。事實上，該定理給出了這樣一個判定USAT問題的隨機算法。

雖然我們尚不知如何提高Unique-SAT問題的隨機算法的準確性，但對於USAT問題的Parity（奇偶性）版本${\displaystyle \oplus SAT}$ （亦即，將前述問題中的“唯一賦值”改為“奇數個賦值”），我們可以通過重複執行隨機算法以提高算法準確性。由此，我們可以通過對多項式譜系的深度採用數學歸納法，得到一個${\displaystyle PH\subseteq BPP^{\oplus P}}$ 的證明（參見：BPP）。注意這個證明實際上給出一個映射${\displaystyle F_{r}}$ （對於每個隨機數取值${\displaystyle r}$ ，存在一個映射${\displaystyle F_{r}}$ ），將每個值為真的多項式譜系實例${\displaystyle \phi }$ 映射到一個${\displaystyle \oplus SAT}$ 的實例${\displaystyle F_{r}(\phi )}$ （亦即，一個有著奇數個真賦值的布爾表達式），而將每個非真的實例映射到一個有偶數個（不一定為0個）真賦值的布爾表達式。

去隨機化

證明的第二部分（去隨機化）將每個${\displaystyle BPP^{\oplus P}}$ 的實例映射到一個${\displaystyle \#SAT}$ 問題。具體而言，去隨機化過程${\displaystyle T}$ 將每個${\displaystyle \oplus SAT}$ 問題的實例${\displaystyle \psi }$ 映射到另一個布爾表達式${\displaystyle T(\psi )}$ ，其真賦值個數（用${\displaystyle \#T(\psi )}$ 表示）模一個大數${\displaystyle R}$ 餘${\displaystyle -1}$ ；另一方面，每個不屬於${\displaystyle \oplus SAT}$ 的布爾表達式${\displaystyle \psi '}$ 則被映射到一個表達式${\displaystyle T(\psi ')}$ ，其真賦值個數${\displaystyle \#T(\psi ')}$ 模同一個大數${\displaystyle R}$ 餘${\displaystyle 0}$ 。

這樣，給定一個多項式譜系內的實例${\displaystyle \phi }$ ，我們可以求以下表達式：

${\displaystyle S(\phi )=\displaystyle \sum _{r}\#T(F_{r}(\phi )).}$ 

在${\displaystyle \phi }$ 本身為真的時候，大多數（例如，多於3/4）的${\displaystyle F_{r}}$ 實例會返回${\displaystyle \oplus SAT}$ 的實例，因此${\displaystyle \#T(F_{r}(\phi ))}$ 會得到${\displaystyle -1}$  (模${\displaystyle R}$ ）；同理，在${\displaystyle \phi }$ 為假的時候，大多數的${\displaystyle \#T(F_{r}(\phi ))}$ 會得到${\displaystyle 0}$ 。因此，在求模的大數${\displaystyle R}$ 足夠大時，這兩個情況（${\displaystyle \phi }$ 為真和為假）所對應的${\displaystyle S(\phi )}$ 的取值區間是不重合的。如果我們能求解${\displaystyle S(\phi )}$ ，則我們可以立即判定任何多項式譜系內的${\displaystyle \phi }$ 是否為真。

但是，注意到上述${\displaystyle S}$ 的表達式的子項數事實上達到了指數級（因為${\displaystyle r}$ 的長度可以是輸入長度的多項式），因此直接求和是不可行的。

一個解決方法是注意到${\displaystyle T(F_{r}(\phi ))}$ 實際上是一個SAT表達式，因此可以考慮下面的SAT問題${\displaystyle Q(\phi )}$ ：“求${\displaystyle (r,x)}$ 使得${\displaystyle T(F_{r}(\phi ))(x)}$ 為真”。注意${\displaystyle Q(\phi )}$ 的真賦值個數等於${\displaystyle S(\phi )}$ 。因此，如果我們能在多項式時間內求解一個#SAT問題（也就${\displaystyle \#Q(\phi )}$ ），我們就可以判定${\displaystyle \phi }$ ，所以${\displaystyle PH}$ 是${\displaystyle P^{\#P}}$ 的一個子集。

參考資料

1. 1998 Gödel Prize. Seinosuke Toda. [2012-12-09]. （原始内容于2010-03-16）. 
2. Toda, Seinosuke, PP is as hard as the polynomial-time hierarchy (PDF), SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics), 1991, 20 (5): 865–877 [2012-12-09], ISSN 1095-7111, doi:10.1137/0220053, （原始内容 (PDF)于2016-03-03）