戶田定理

在理論計算機科學的複雜度理論這一分支中，戶田定理是一個重要的結果，它指出在多項式譜系和之間的內在聯繫：

:PH \subseteq P^{\#P}.

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

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

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

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

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

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

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

:S(\phi) = \displaystyle \sum_{r} \#T(F_r(\phi)).

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

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

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

參考資料