基本介紹
- 中文名：多項式時間歸約
- 理論：計算複雜性理論
- 相關術語：自歸約
- 學科：運籌學
- 領域：運籌學
簡介,定義,引申定理,歸約技巧,自歸約,
簡介
定義
多項式時間歸約：如果問題X和問題Y滿足以下兩條性質，那么問題X可以在多項式時間歸約到問題Y。
- 問題X可以通過多項式時間的基本運算步驟轉換為問題Y；
- 問題X多項式次調用求解問題Y的算法，且問題Y可以在多項式時間內被求解。
可以記為：X ≤p Y
需要注意的是，問題X轉換為問題Y之後，問題Y的運行時間是建立在問題Y的輸入上。
對於這個定義，可以簡單理解為：求解問題Y算法需要多項式時間，問題X轉換為問題Y需要多項式個基本運算加上多項式次調用求解問題Y的算法。因此總共需要的時間是：多項式 + 多項式 * 多項式。
引申定理
根據以上定義，可以得到三個定理：
- 假設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的點覆蓋，那么就可以判定該頂點是最小點覆蓋中的頂點，不斷重複這個操作，就可以找到最小點覆蓋。
