歸約

英文
Reduction
編輯本段
定義
歸約是使用解決其它問題的"黑盒"來解決另一個問題.
編輯本段
套用
假設有一個複雜的問題P,而它看起來與一個已知的問題Q很相似,可以試著在兩個問題間找到一個歸約(reduction,或者transformation).
對於問題的先後,歸約可以達到兩個目標:
(1)已知Q的算法,那么就可以把使用了Q的黑盒的P的解決方法轉化成一個P的算法.
(2)如果P是一個已知的難題,或者特別地,如果P的下限,那么同樣的下限也可能適用於Q.前一個歸約是用於獲取P的信息;而後者則是用於獲取Q的信息.