變換_(複雜度)

在可計算性理論與計算複雜性理論中，所謂的**歸約**是將某個計算問題轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。

以直覺觀之，如果存在能有效解決問題 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}$ 乘法（因為每個合法的整數平方式 n2 都可歸約成乘法 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.