跳至內容

戶田定理

維基百科,自由的百科全書

在理論計算機科學複雜度理論這一分支中,戶田定理是一個重要的結果,它指出在多項式譜系計數問題英語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)