Example of a reduction from the boolean satisfiability problem (A ∨ B ) ∧ (¬A ∨ ¬B ∨ ¬C ) ∧ (¬A ∨ B ∨ C ) to a vertex cover problem . The blue vertices form a minimum vertex cover, and the blue vertices in the gray oval correspond to a satisfying truth assignment for the original formula.
在可計算性理論 與計算複雜性理論 中,所謂的歸約 是將某個計算問題 轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類 (因轉換過程而異)。
以直覺觀之,如果存在能有效解決問題 B的算法,也可以作為解決問題A的子程序,則將問題A稱為「可歸約」到問題B,因此求解A並不會比求解B更困難。
一般寫作A ≤m B,通常也在≤符號下標使用的歸約類型(m:映射縮小,p:多項式縮減)。
將一組問題歸約到特定類型所產生的數學結構,通常形成预序关系 ,其等價類可用於定義求解難度和複雜度。
簡易介紹
以乘法與平方為例的多一歸約 示意圖。
我們解題時常遇見似曾相識的題目。此時,我們若可將新題轉換成已解舊題的一例,則新題亦解矣。
另一更微妙的用法是:若我們擁有一個已證明難以解決的問題,我們又獲得另一個相似 的新問題。我們可合理推想此新問題亦是難以解決的。我們可由下列謬證法得證:若此新問題本質上容易解答,且若我們可展示每個舊問題的實例可經由一系列轉換步驟變成新問題的實例,則舊問題便容易解決,因此得到悖論。因此新問題可知亦難以解決。
一個歸約簡例是從乘法 化成平方 。設想我們僅能以加、減、平方與除以二 等操作,我們可運用此知識並結合下列方程式,以取得任兩數的乘積:
a
× × -->
b
=
(
(
a
+
b
)
2
− − -->
a
2
− − -->
b
2
)
2
{\displaystyle a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}}
我們亦可從另一方向歸約此問題:顯然地,若我們可以乘以任兩數,則我們可以對任一數平方:
a
2
=
a
× × -->
a
{\displaystyle a^{2}=a\times a}
因此可見兩問題之難度似乎相等,此類歸約稱為圖靈歸約 。上題的圖靈歸約關係為:
乘法
≤ ≤ -->
T
{\displaystyle \leq _{T}}
平方且 平方
≤ ≤ -->
T
{\displaystyle \leq _{T}}
乘法
然而,若我們增加條件:「此運算只能使用平方一次,且只能在結尾使用」,則更難尋找合適歸約。在這條件下,即使我們使用所有基礎運算,包括乘法,也找不到適當的歸約步驟。因為我們不僅要運算有理數,也必須運算像是
2
{\displaystyle {\sqrt {2}}}
的無理數 。而另一方向的歸約,我們的確可用一次乘法簡單地平方任何數,且此乘法的確是最後的運算。將此限制形式導入歸約中,我們已展示其歸約結論:普遍來說,乘法的確難於平方。此歸約稱為多一歸約 。上題的多一歸約關係為:
平方
≤ ≤ -->
m
{\displaystyle \leq _{m}}
乘法(因為每個合法的整數平方式n2 都可歸約成乘法n×n,但反之不然)
定義
給予兩個自然數 N 的子集 A 與B ,以及一個函數 集合F ,型態為由N至N ,並擁有複合 封閉性。我們稱在F下,A可歸約成B 若:
∃ ∃ -->
f
∈ ∈ -->
F
.
∀ ∀ -->
x
∈ ∈ -->
N
.
x
∈ ∈ -->
A
⇔ ⇔ -->
f
(
x
)
∈ ∈ -->
B
{\displaystyle \exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B}
我們寫做:
A
≤ ≤ -->
F
B
{\displaystyle A\leq _{F}B}
設S 為P (N )(即自然数集的幂集 )的子集,另設≤的歸約關係,則S 稱做封閉 於≤之下若:
∀ ∀ -->
s
∈ ∈ -->
S
.
∀ ∀ -->
A
∈ ∈ -->
P
(
N
)
.
A
≤ ≤ -->
s
⇔ ⇔ -->
A
∈ ∈ -->
S
{\displaystyle \forall s\in S{\mbox{ . }}\forall A\in P(\mathbb {N} ){\mbox{ . }}A\leq s\Leftrightarrow A\in S}
一N 的子集A ,稱對S困難(hard) ,若:
∀ ∀ -->
s
∈ ∈ -->
S
.
s
≤ ≤ -->
A
{\displaystyle \forall s\in S{\mbox{ . }}s\leq A}
一N 的子集A ,若A 對S 困難且A 包含於S 集合之內,則稱A對S完備(complete) 。
复杂性类的判别
詳例
下例利用從停機問題至某個語言的轉換,以證明該語言是不可決定的。設H (M ,w )是問題:「判定給定的圖靈機 M 會否在輸入字串w 後停機(接受或拒絕此字串)」。此語言已知是不可決定的[ 1] 。又設E (M )是問題:「給定圖靈機M ,判定它所接受的語言是否空(意即M 是否接受任何字串)」。我們可以藉由從H 歸約成E 以顯示E 也是不可決定的。
為了獲得悖論,假設R 是E 的一個仲裁機器 (即一定會停的圖靈機),我們將用此機器R 產生問題H 的仲裁機器S 。給予輸入資料——一個圖靈機M 與某些輸入字串w ,定義圖靈機S (M ,w ):S 創造一個圖靈機N ,N 僅接受輸入圖靈機M 時會停止的字串w ,輸入其他字串則N 進入無窮迴圈。仲裁機器S 現在可評估R (N ),以驗證被N 接受的語言是否為空集合。如果R 接受N ,則被N 接受的語言是空集合,所以M 不會在輸入為w 時停止,所以S 可以拒絕。如果R 拒絕N ,則被N 接受的語言是非空集合,則M 不會在輸入為w 時停止,故S 可接受。因此若我們有了E 的一仲裁機器R ,則我們將能產生停機問題H (M ,w )及任何機器M 與任何輸入字串w 的仲裁機器S 。但我們已知此S 絕對不存在,故得矛盾。因此可知語言E 同樣也是不可決定的。
註
歸約亦是一種預序關係 ,意指在P (N )×P (N ),此P (N )上擁有自反關係 與傳遞關係 ,此處的P (N )是自然數 的冪集 (power set)。
若在某個複雜度類別上的所有問題都可歸約成某問題P ,則可稱P 是完備(complete)的,且P 自己也會處於此類別中。故問題P 代表此類別,因其任一解 都可經由歸約解決此類別中的所有問題。[ 2]
歸約種類與應用
依上例所述,在計算複雜度中,主要有兩大類的歸約:多一歸約 與圖靈歸約 。多一歸約將一問題的所有實例對應到另一問題的實例上;圖靈歸約計算 一問題的解,並假設其他問題容易解決。多一歸約強於圖靈歸約。較弱的歸約在分割問題的種類上效率較高,但它們的威力較弱,使本類歸約較難設計。
然而,為了使歸約有用,它們必須易於使用。例如實際研究中常常要將難以得解的NP完備 問題,例如SAT 問題,歸約成顯而易懂的問題,像藉由效率為指數時間 並在有解時輸出整數零的機器,決定一數是否為零。但這並沒有多少用處,因為我們可以執行如同解決舊問題一樣難的歸約以解決新問題。
因此,依照複雜度類別使用適當歸約符號的學問興起。在鑽研複雜度類NP 與更難的類別時,我們使用多項式時間多一歸約 。在多項式譜系 中定義類別時,我們使用多項式時間圖靈歸約 。當我們在類別P 之內學習NC 與NL 類別時,我們使用對數空間歸約 。歸約也用在可計算性理論 中,以顯示問題是否可不可被任何機器解決;在此情境下,歸約僅侷限於可計算函數 上。
参考文献
^ 例如:存档副本 . [2007-01-06 ] . (原始内容 存档于2007-01-17).
^ Thomas H. Cormen, Introduction to Algorithm, second edition, page. 970, figure 34.1.
參閱
文獻
(英文) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, 2001, ISBN 978-0-262-03293-3
(英文) Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0-262-68052-3 .
(英文) Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3-540-66752-0 .
(英文) E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0-444-89882-1 .
易解复杂度类
怀疑难解复杂度类 难解复杂度类 复杂度类的谱系 相关复杂度族