來源：互聯(lián)網(wǎng)
歸約是計算理論中的一個基本概念，它涉及將一個問題轉換為另一個問題的過程。在可計算性理論與計算復雜性理論中，歸約不僅用于解決問題，還用于定義問題的復雜度類別。如果問題A可以歸約到問題B，并且存在解決問題B的有效算法，那么問題A至少和問題B一樣容易解決。歸約也是一種預序關系，它在自然數(shù)的冪集上擁有自反關系與傳遞關系。若在某個復雜度類別上的所有問題都可歸約成某問題P，則可稱P是完備（complete）的，且P自己也會處于此類別中。
簡介
定義
歸約是使用解決其他問題的"黑箱"來解決另一個問題。在更正式的定義中，給定兩個自然數(shù)集合A與B，如果存在一個函數(shù)集合F，使得對于所有自然數(shù)x，x屬于A當且僅當f(x)屬于B，那么我們說A可以歸約到B。
應用
歸約的應用包括但不限于以下兩個方面：
1. 如果已知問題Q的算法，那么可以將問題P歸約到Q，從而得到解決P的算法。
2. 如果P是一個已知的難題，那么通過歸約，可以推斷出Q也可能是一個難題。
復雜性類的判別
歸約在復雜性類別的判別中扮演著重要角色。例如，如果一個問題可以通過多項式時間歸約到已知的NP完備問題，那么這個問題也被認為是NP完備的。復雜度類P、NP與PSPACE具有多項式時間歸約的封閉性，而L、NL、P、NP與PSPACE則具有對數(shù)空間歸約的封閉性。
歸約種類與應用
在計算復雜度中，主要有兩大類的歸約：多一歸約與圖靈歸約。多一歸約將一個問題的所有實例對應到另一個問題的實例上，而圖靈歸約則假設其他問題容易解決，并計算一個問題的解。多一歸約在分割問題的種類上效率較高，但它們的威力較弱，使本類歸約較難設計。依照復雜度類別使用適當歸約符號的學問興起，例如在鉆研復雜度類NP與更難的類別時，我們使用多項式時間多一歸約。
參考資料 >