標籤: 暫無標籤

歸約,是使用解決其它問題的"黑盒"來解決另一個問題.

英文

  Reduction
編輯本段
定義

  歸約是使用解決其它問題的"黑盒"來解決另一個問題.
編輯本段
應用

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

上一篇[穆切]    下一篇 [洪崖]

相關評論

同義詞:暫無同義詞