在計算復雜性理論中，多項式時間歸約是指假設已有解決一個問題的子程序，利用它在多項式時間內（不考慮子程序運行所用時間）解決另一個問題的歸約方法。如果將第一個問題轉換成第二個問題的時間，且子程序被調用的次數都是多項式級別的，那么第一個問題可以多項式時間歸約到第二個問題。多項式時間歸約證明了第一個問題不比第二個問題難，因為當第二個問題存在高效率算法時，第一個也存在。反之，如果第一個問題沒有高效率算法時，第二個也沒有。計算復雜性理論中經常使用多項式時間歸約來定義復雜性類和完全問題。
定義
多項式時間歸約：如果問題X和問題Y滿足以下兩條性質，那么問題X可以在多項式時間歸約到問題Y。
- 問題X可以通過多項式時間的基本運算步驟轉換為問題Y；
- 問題X多項式次調用求解問題Y的算法，且問題Y可以在多項式時間內被求解。
可以記為：X ≤p Y
需要注意的是，問題X轉換為問題Y之后，問題Y的運行時間是建立在問題Y的輸入上。
對于這個定義，可以簡單理解為：求解問題Y算法需要多項式時間，問題X轉換為問題Y需要多項式個基本運算加上多項式次調用求解問題Y的算法。因此總共需要的時間是：多項式 + 多項式 * 多項式。
規約的類型
多項式時間歸約有幾種不同類型，取決于具體如何使用子程序。三種最常見的多項式時間歸約類型，從最多限制到最少限制的，是多項式時間多一歸約（Karp歸約）、真值表歸約和圖靈歸約（Cook歸約）。
多一歸約
多一歸約（Karp歸約）是將問題A的輸入轉換成問題B的輸入的多項式算法，使得轉換后的問題與原問題有相同的輸出。問題A的實例x可以通過此轉換為問題B的實例y，將y輸入解決問題B的算法，然后返回它的輸出。
真值表歸約
真值表歸約是將問題A的輸入轉換成固定數量個問題B的輸入的多項式算法，使得原問題的輸出可以被表示為問題B輸出的函數。將B的輸出映射到A的輸出的函數對于所有輸入必須相同，所以它可以用真值表表示。
圖靈歸約（Cook歸約）是一種算法，它需要調用問題B的子程序多項式次，以及這些子程序調用之外的多項式時間來解決問題A。多一歸約可以被視為圖靈歸約的受限變體，其中對問題B的子程序的調用次數恰好為1，且歸約返回的值與子程序返回的值相同。
引申定理
根據以上定義，可以得到三個定理：
- 假設X ≤p Y，如果Y能夠在多項式時間內求解，那么X也能在多項式時間內求解。
- 假設X ≤p Y，如果X不能在多項式時間內求解，那么Y也不能在多項式時間內求解。
- 如果X ≤p Y且Y ≤p X，那么X和Y是等價的。
歸約技巧
歸約的幾種技巧：
1. 簡單的恒等歸約：比如最大獨立集和最小點覆蓋。
2. 從特殊情況到一般情況：比如點覆蓋 ≤p 集合覆蓋。
3. 利用gadgets：比如3-SAT ≤p 獨立集。
自歸約
自歸約：將求解問題歸約成判斷問題，如果判斷問題能夠解決，那么就可以利用判斷問題來解決求解問題。
比如最小點覆蓋問題，假如我們能判斷一個圖中是否存在點數為k的最小點覆蓋。于是可以遍歷圖中的每個頂點，如果刪去這個頂點以及和這個頂點相連接的邊，圖中只存在點數為k-1的點覆蓋，那么就可以判定該頂點是最小點覆蓋中的頂點，不斷重復這個操作，就可以找到最小點覆蓋。
參考資料 >