查看“︁戶田定理”︁的源代码

在理論[[計算機科學]]的[[複雜度理論]]這一分支中，戶田定理是一個重要的結果，它指出在[[PH (複雜度)|多項式譜系]]和{{link-en|計數問題|Counting problem (complexity)}}之間的內在聯繫：

:<math>PH \subseteq P^{\#P}.</math>

根據戶田定理，多項式譜系內的所有問題均可以在[[多項式時間]]內[[歸約]]為求解多項式個（實際上可以規約為1個）“求令給定布爾表達式為真的可能賦值的數量”（#SAT）問題（參見：[[布尔可满足性问题]]）。戶田定理的証明由{{link-en|戶田誠之助|Seinosuke Toda}}在1991年給出，並在1998年為証明者贏得了當年的[[哥德爾獎]]<ref>{{Cite web |url=http://sigact.acm.org/Prizes/Godel/1998.html |title=1998 Gödel Prize. Seinosuke Toda |accessdate=2012-12-09 |archive-date=2010-03-16 |archive-url=https://web.archive.org/web/20100316230639/http://sigact.acm.org/prizes/godel/1998.html |dead-url=no }}</ref>。（在1991年的該篇論文<ref>{{Citation | last1=Toda | first1=Seinosuke | title=PP is as hard as the polynomial-time hierarchy | url=http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf | publisher=[[Society for Industrial and Applied Mathematics]] | location=Philadelphia | year=1991 | journal=[[SIAM Journal on Computing]] | issn=1095-7111 | volume=20 | issue=5 | pages=865–877 | doi=10.1137/0220053 | accessdate=2012-12-09 | archive-date=2016-03-03 | archive-url=https://web.archive.org/web/20160303170125/http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf | dead-url=no }}</ref>中，戶田誠之助實際上證明了<math>PH \subseteq P^{PP}</math>（參見：[[PP]]），而上述結果是這個結果的一個自然推論。）

戶田定理的証明主要包含以下兩部分：
* 一個概率性的証明指出<math>PH \subseteq BPP^{\oplus P}</math>；
* 通過去隨機化過程証明上述復雜度類在<math>P^{\#P}</math>內。

== <math>PH \subseteq BPP^{\oplus P}</math> ==

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

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

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

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

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

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

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

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

==參考資料==
{{reflist}}
[[Category:計算複雜性理論]]
[[Category:数学定理]]
[[Category:包含证明的条目]]