查看“︁歸約”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
|1=zh-tw:簡化;zh-cn:归約;
}}
[[File:3SAT reduced too VC.svg|thumb|300px|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.]]
在[[可計算性理論]]與[[計算複雜性理論]]中，所謂的'''歸約'''是將某個{{tsl|en|computational problem|計算問題}}轉換為另一個問題的過程。可用歸約法定義某些問題的[[複雜度類]]（因轉換過程而異）。

以直覺觀之，如果存在能有效[[解決問題]]B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。

一般寫作A ≤<sub>m</sub> B，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。

將一組問題歸約到特定類型所產生的數學結構，通常形成[[预序关系]]，其等價類可用於定義求解難度和複雜度。

== 簡易介紹 ==
[[File:many-one-reduction.jpg|thumb|300px|以乘法與平方為例的[[多一歸約]]示意圖。]]
我們解題時常遇見似曾相識的題目。此時，我們若可將新題轉換成已解舊題的一例，則新題亦解矣。

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

一個歸約簡例是從'''乘法'''化成'''平方'''。設想我們僅能以加、減、平方與[[除以二]]等操作，我們可運用此知識並結合下列方程式，以取得任兩數的乘積：
: <math>a \times b = \frac{\left(\left(a + b\right)^{2} - a^{2} - b^{2}\right)}{2}</math>

我們亦可從另一方向歸約此問題：顯然地，若我們可以乘以任兩數，則我們可以對任一數平方：
: <math>a^{2} = a \times a</math>

因此可見兩問題之難度似乎相等，此類歸約稱為[[圖靈歸約]]。上題的圖靈歸約關係為：
:乘法<math> \leq_T </math>平方且 平方<math> \leq_T </math>乘法

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

== 定義 ==
給予兩個[[自然數]]'''N'''的[[子集]]'''A'''與'''B'''，以及一個[[函數]]集合'''F'''，型態為'''由N至N'''，並擁有[[複合函數|複合]]封閉性。我們稱'''在F下，A可歸約成B'''若：
:<math>\exists f \in F \mbox{ . } \forall x \in \mathbb{N} \mbox{ . } x \in A \Leftrightarrow f(x) \in B</math>

我們寫做：
:<math>A \leq_{F} B</math> 

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

:<math>\forall s \in S \mbox{ . } \forall A \in P(\mathbb{N}) \mbox{ . } A \leq s \Leftrightarrow A \in S</math>

一'''N'''的子集'''A'''，稱'''對S困難（hard）'''，若：
:<math>\forall s \in S \mbox{ . } s \leq A</math>
 
一'''N'''的子集'''A'''，若'''A'''對'''S'''困難且'''A'''包含於'''S'''集合之內，則稱'''A對S完備（complete）'''。

== 复杂性类的判别 ==
{{main|复杂性类}}
* 若要證明一[[決定性問題|問題]]是不可在決定的，我们可以一[[可計算函數]]將它轉換成另一已知不可決定的問題，例如，欲證P是不可決定的，可試將[[停機問題]]化約成問題P。
* 複雜度類[[P (複雜度)|P]]、[[NP (複雜度)|NP]]與[[PSPACE]]擁有[[多項式時間]]歸約的封閉性。
* 複雜度類[[L (複雜度)|L]]、[[NL (複雜度)|NL]]、[[P (複雜度)|P]]、[[NP (複雜度)|NP]]與[[PSPACE]]擁有[[對數空間歸約]]的封閉性。

=== 詳例 ===
{{main|停机问题}}
下例利用從停機問題至某個語言的轉換，以證明該語言是不可決定的。設'''H'''('''M''','''w''')是問題：「判定給定的[[圖靈機]]'''M'''會否在輸入字串'''w'''後停機（接受或拒絕此字串）」。此語言已知是不可決定的<ref>例如：{{cite web |url=http://cs.wwc.edu/KU/Logic/turingMachine.html |title=存档副本 |accessdate=2007-01-06 |deadurl=yes |archiveurl=https://web.archive.org/web/20070117105102/http://cs.wwc.edu/KU/Logic/turingMachine.html |archivedate=2007-01-17 }}</ref>。又設'''E'''('''M''')是問題：「給定圖靈機'''M'''，判定它所接受的語言是否空（意即'''M'''是否接受任何字串）」。我們可以藉由從'''H'''歸約成'''E'''以顯示'''E'''也是不可決定的。

為了獲得悖論，假設'''R'''是'''E'''的一個{{tsl|en|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'''代表此類別，因其'''任一解'''都可經由歸約解決此類別中的所有問題。<ref>Thomas H. Cormen, Introduction to Algorithm, second edition, page. 970, figure 34.1.</ref>

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

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

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

== 参考文献 ==
{{reflist}}

== 參閱 ==
* [[多一歸約]]
* [[真值表歸約]]
* [[圖靈歸約]]
* [[Comparison of numberings]]
* [[優化 (計算機)]]

== 文獻 ==
* {{en}} Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, 2001, ISBN 978-0-262-03293-3
* {{en}} Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0-262-68052-3.
* {{en}} Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3-540-66752-0.
* {{en}} E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0-444-89882-1.

{{复杂度类}}
{{Authority control}}
[[Category:歸約]]