多項式時間歸約

在計算複雜性理論中，多項式時間歸約是指假設已有解決一個問題的子程序，利用它在多項式時間內（不考慮子程序運行所用時間）解決另一個問題的歸約方法。如果將第一個問題轉換成第二個的時間，且子程序被調用的次數都是多項式級別的，那麼第一個問題可以多項式時間規約到第二個問題。^[1]

多項式時間規約證明了第一個問題不比第二個問題難。因為當第二個問題存在高效率算法時，第一個也存在。因為逆否命題，如果第一個問題沒有高效率算法時，第二個也沒有。^[1]計算複雜性理論中經常使用多項式時間規約來定義複雜性類和完全問題。

規約的類型

多項式時間歸約有幾種不同類型，取決於具體如何使用子程序。

三種最常見的多項式時間規約類型，從最多限制到最少限制的，是多項式時間多一規約（英語：Many-one reduction），真值表規約（英語：Truth-table reductions），圖靈規約。^[2]最常用的是多一規約，在某些情況下短語「多項式時間規約」可能僅指多項式時間多一規約。^[3]

多一規約

從問題A到問題B（兩個通常都需要是決定性問題）的多項式時間多一規約（英語：Many-one reduction），是將問題A的輸入轉換成問題B的輸入的多項式算法，使得轉換後的問題與原問題有相同的輸出。問題A的實例x，可以通過此轉換為問題B的實例y，將y輸入解決問題B的算法，然後返回它的輸出。多項式時間多一規約也被稱為Karp規約，以理查德·卡普命名。這種類型的規約被表示為${\displaystyle A\leq _{m}^{P}B}$或${\displaystyle A\leq _{p}B}$。^[4][5]

真值表歸約

從問題A到問題B（兩個都是決定性問題）的多項式時間真值表規約（英語：Truth-table reductions），是將問題A的輸入轉換成固定數量個問題B的輸入的多項式算法，使得原問題的輸出可以被表示為問題B輸出的函數。將 B 的輸出映射到 A 的輸出的函數對於所有輸入必須相同，所以它可以用真值表表示。 這種類型的歸約可以用表達式${\displaystyle A\leq _{tt}^{P}B}$來表示。^[6]

圖靈規約

從問題 A 到問題 B 的多項式時間圖靈規約是一種算法，它需要調用問題 B 的子程序多項式次，以及這些子程序調用之外的多項式時間來解決問題 A。 多項式時間圖靈規約也稱為庫克規約，以史蒂芬·庫克命名。 這種類型的歸約可以用表達式${\displaystyle A\leq _{T}^{P}B}$來表示。^[4]多一歸約可以被視為圖靈歸約的受限變體，其中對問題 B 的子程序的調用次數恰好為 1，且歸約返回的值與子程序返回的值相同。

參考文獻

1. Kleinberg, Jon; Tardos, Éva. Algorithm Design. Pearson Education. 2006: 452–453. ISBN 978-0-321-37291-8.
2. Mandal, Debasis; Pavan, A.; Venugopalan, Rajeswari. Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science. 2014 [2022-08-11]. ISBN 978-3-939897-77-4. （原始內容存檔於2022-06-17）.
3. Wegener, Ingo, Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer: 60, 2005, ISBN 9783540274773.
4. Goldreich, Oded, Computational Complexity: A Conceptual Perspective, Cambridge University Press: 59–60, 2008, ISBN 9781139472746
5. 黃文奇; 陳志祥. 递归集的k-1-度上半格的不可补性与不可分配性. 數學學報. 1989-08-29, (04): 517-524 [2022-08-11]. ISSN 0583-1431. （原始內容存檔於2022-08-11） （中文（中國大陸））.
6. Buss, S.R.; Hay, L., On truth-table reducibility to SAT and the difference hierarchy over NP, Proceedings of Third Annual Structure in Complexity Theory Conference: 224–233, 1988, CiteSeerX 10.1.1.5.2387 , ISBN 978-0-8186-0866-7, doi:10.1109/SCT.1988.5282.