Polynomial Reduction
多項式帰着は問題 A を問題 B へ多項式時間で変換するものである。B が解けるなら A も解け、NP 困難性の証明に用いられる。
目的
問題の困難性を証明し、解可能性を移すための、計算量理論の中核的な道具である。
メカニズム
A ≤_p B：多項式時間の関数 f が A のインスタンスを B のインスタンスへ写像し、A(x)=B(f(x)) が成り立つ。B が P に属すれば A も P に属する。A が NP 困難と知られ、かつ A ≤_p B ならば、B も NP 困難となる。
ユースケース
- 複雑性を証明すること
- NP 困難への帰着
- 問題を分類すること