戶田定理

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

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

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

  • 一個概率性的証明指出
  • 通過去隨機化過程証明上述復雜度類在內。

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

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

去隨機化

證明的第二部分(去隨機化)將每個 的實例映射到一個 問題。具體而言,去隨機化過程 將每個 問題的實例 映射到另一個布爾表達式 ,其真賦值個數(用 表示)一個大數  ;另一方面,每個不屬於 的布爾表達式 則被映射到一個表達式 ,其真賦值個數 模同一個大數  

這樣,給定一個多項式譜系內的實例 ,我們可以求以下表達式:

 

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

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

一個解決方法是注意到 實際上是一個SAT表達式,因此可以考慮下面的SAT問題 :“求 使得 為真”。注意 的真賦值個數等於 。因此,如果我們能在多項式時間內求解一個#SAT問題(也就 ),我們就可以判定 ,所以  的一個子集。

參考資料

  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)