戶田定理

戶田定理是理論計算機科學的複雜度理論的重要結果，它指出在多項式譜系和計數問題之間的內在聯繫。

基本介紹

• 中文名：戶田定理
• 提出者：戶田誠之助
• 提出時間：1991年
• 套用學科：理論計算機科學

定義

根據戶田定理，多項式譜系內的所有問題均可以在多項式時間內歸約為求解多項式個（實際上可以規約為1個）“求令給定布爾表達式為真的可能賦值的數量”（#SAT）問題（參見：布爾可滿足性問題）。戶田定理的證明由戶田誠之助（英語：SeinosukeToda）在1991年給出，並在1998年為證明者贏得了當年的哥德爾獎。（在1991年的該篇論文中，戶田誠之助實際上證明了（參見：PP），而上述結果是這個結果的一個自然推論。）
戶田定理的證明主要包含以下兩部分：
一個機率性的證明指出；
通過去隨機化過程證明上述複雜度類在P#P內。

機率性

第一部分的證明基於瓦里安特·瓦茲拉尼定理（英語：valiant-Vaziranitheorem）。該定理指出如果唯一SAT(Unique-SAT，或USAT)問題（亦即，僅在一個布爾表達式沒有令其為真的賦值，和在有一個唯一的賦值之間做出判定，而對於有一個以上真賦值的布爾表達式可做任何輸出）有一個多項式的隨機化算法，則（參見：RP(複雜度)）。事實上，該定理給出了這樣一個判定USAT問題的隨機算法。
雖然我們尚不知如何提高Unique-SAT問題的隨機算法的準確性，但對於USAT問題的Parity（奇偶性）版本（亦即，將前述問題中的“唯一賦值”改為“奇數個賦值”），我們可以通過重複執行隨機算法以提高算法準確性。由此，我們可以通過對多項式譜系的深度採用數學歸納法，得到一個的證明（參見：BPP）。注意這個證明實際上給出一個映射（對於每個隨機數取值，存在一個映射），將每個值為真的多項式譜系實例映射到一個的實例（亦即，一個有著奇數個真賦值的布爾表達式），而將每個非真的實例映射到一個有偶數個（不一定為0個）真賦值的布爾表達式。

去隨機化

證明的第二部分（去隨機化）將每個的實例映射到一個問題。具體而言，去隨機化過程將每個問題的實例映射到另一個布爾表達式，其真賦值個數（用表示）模一個大數余；另一方面，每個不屬於的布爾表達式則被映射到一個表達式，其真賦值個數模同一個大數余。
這樣，給定一個多項式譜系內的實例，我們可以求以下表達式：
在本身為真的時候，大多數（例如，多於3/4）的實例會返回的實例，因此會得到(模）；同理，在為假的時候，大多數的會得到。因此，在求模的大數足夠大時，這兩個情況（為真和為假）所對應的的取值區間是不重合的。如果我們能求解，則我們可以立即判定任何多項式譜系內的是否為真。
但是，注意到上述的表達式的子項數事實上達到了指數級（因為的長度可以是輸入長度的多項式），因此直接求和是不可行的。
一個解決方法是注意到實際上是一個SAT表達式，因此可以考慮下面的SAT問題：“求使得為真”。注意的真賦值個數等於。因此，如果我們能在多項式時間內求解一個#SAT問題（也就），我們就可以判定，所以是的一個子集。