歸約

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\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}$

我們亦可從另一方向歸約此問題：顯然地，若我們可以乘以任兩數，則我們可以對任一數平方：

$a^{2}=a\times a$

因此可見兩問題之難度似乎相等，此類歸約稱為圖靈歸約。上題的圖靈歸約關係為：

乘法$\leq _{T}$平方且 平方$\leq _{T}$乘法

然而，若我們增加條件：「此運算只能使用平方一次，且只能在結尾使用」，則更難尋找合適歸約。在這條件下，即使我們使用所有基礎運算，包括乘法，也找不到適當的歸約步驟。因為我們不僅要運算有理數，也必須運算像是${\sqrt {2}}$的無理數。而另一方向的歸約，我們的確可用一次乘法簡單地平方任何數，且此乘法的確是最後的運算。將此限制形式導入歸約中，我們已展示其歸約結論：普遍來說，乘法的確難於平方。此歸約稱為多一歸約。上題的多一歸約關係為：

平方$\leq _{m}$乘法（因為每個合法的整數平方式n²都可歸約成乘法n×n，但反之不然）

定義

給予兩個自然數N的子集A與B，以及一個函數集合F，型態為由N至N，並擁有複合封閉性。我們稱在F下，A可歸約成B若：

$\exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B$

我們寫做：

$A\leq _{F}B$

設S為P(N)（即自然数集的幂集）的子集，另設≤的歸約關係，則S稱做封閉於≤之下若：

$\forall s\in S{\mbox{ . }}\forall A\in P(\mathbb {N} ){\mbox{ . }}A\leq s\Leftrightarrow A\in S$

一N的子集A，稱對S困難（hard），若：

$\forall s\in S{\mbox{ . }}s\leq A$

一N的子集A，若A對S困難且A包含於S集合之內，則稱A對S完備（complete）。

复杂性类的判别

主条目：复杂性类

• 若要證明一問題是不可在決定的，我们可以一可計算函數將它轉換成另一已知不可決定的問題，例如，欲證P是不可決定的，可試將停機問題化約成問題P。
• 複雜度類P、NP與PSPACE擁有多項式時間歸約的封閉性。
• 複雜度類L、NL、P、NP與PSPACE擁有對數空間歸約的封閉性。

詳例

主条目：停机问题

下例利用從停機問題至某個語言的轉換，以證明該語言是不可決定的。設H(M,w)是問題：「判定給定的圖靈機M會否在輸入字串w後停機（接受或拒絕此字串）」。此語言已知是不可決定的。又設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代表此類別，因其任一解都可經由歸約解決此類別中的所有問題。

歸約種類與應用

依上例所述，在計算複雜度中，主要有兩大類的歸約：多一歸約與圖靈歸約。多一歸約將一問題的所有實例對應到另一問題的實例上；圖靈歸約計算一問題的解，並假設其他問題容易解決。多一歸約強於圖靈歸約。較弱的歸約在分割問題的種類上效率較高，但它們的威力較弱，使本類歸約較難設計。

然而，為了使歸約有用，它們必須易於使用。例如實際研究中常常要將難以得解的NP完備問題，例如SAT問題，歸約成顯而易懂的問題，像藉由效率為指數時間並在有解時輸出整數零的機器，決定一數是否為零。但這並沒有多少用處，因為我們可以執行如同解決舊問題一樣難的歸約以解決新問題。

因此，依照複雜度類別使用適當歸約符號的學問興起。在鑽研複雜度類NP與更難的類別時，我們使用多項式時間多一歸約。在多項式譜系中定義類別時，我們使用多項式時間圖靈歸約。當我們在類別P之內學習NC與NL類別時，我們使用對數空間歸約。歸約也用在可計算性理論中，以顯示問題是否可不可被任何機器解決；在此情境下，歸約僅侷限於可計算函數上。

參閱

• 多一歸約
• 真值表歸約
• 圖靈歸約
• Comparison of numberings
• 優化 (計算機)

文獻

• （英文） 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.