可變換 (複雜度)

维基百科，自由的百科全书

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

以直覺觀之，「問題A可變換為問題B」，指問題B的答案可用於解決問題A。因此解決A不會難於解決B。吾輩寫作 A ≤ B，通常也在≤符號下標使用的變換手法。

[编辑] 簡易介紹

以乘法與平方為例的多一變換示意圖。

我們解題時常遇見似曾相識的題目。此時，我們若可將新題轉換成已解舊題的一例，則新題亦解矣。

另一更微妙的用法是：若我們擁有一個已證明難以解決的問題，我們又獲得另一個相似的新問題。我們可合理推想此新問題亦是難以解決的。我們可由下列謬證法得證：若此新問題本質上容易解答，且若我們可展示每個舊問題的實例可經由一系列轉換步驟變成新問題的實例，則舊問題便容易解決，因此得到悖論。因此新問題可知亦難以解決。

一個變換簡例是從乘法化成平方。設想我們僅能以加、減、平方與除以二等操作，我們可運用此知識並結合下列方程式，以取得任兩數的乘積：

a × b = ((a + b)² - a² - b²)/2.

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

a² = a × a.

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

乘法 $\leq_T$ 平方且平方 $\leq_T$ 乘法

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

平方 $\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擁有多項式時間變換（polynomial-time reduction）的封閉性。
複雜度類L、NL、P、NP與PSPACE擁有對數空間變換（log-space reduction）的封閉性

[编辑] 詳例

下例利用從停機問題至某個語言的轉換，以證明該語言是不可決定的。設H(M,w)是問題：「判定給定的圖靈機M會否在輸入字串w後停機（接受或拒絕此字串）」。此語言已知是不可決定的^[1]。又設E(M)是問題：「給定圖靈機M ，判定它所接受的語言是否空（意即M是否接受任何字串）」。我們可以藉由從H變換成E以顯示E也是不可決定的。

為了獲得悖論，假設R是E的一個仲裁機器（decider）(即一定會停的圖靈機)，我們將用此機器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類別時，我們使用對數空間變換。變換也用在可計算性理論中，以顯示問題是否可不可被任何機器解決；在此情境下，變換僅侷限於可計算函數上。

[编辑] 参考文献

↑ 例如：http://cs.wwc.edu/KU/Logic/turingMachine.html
↑ Thomas H. Cormen, Introduction to Algorithm, second edition, page. 970, figure 34.1.

[编辑] 參閱

多一變換
真值表變換
圖靈變換
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-0262680523.
（英文） Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3540667520.
（英文） E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0444898821.