帰着
from 還元可能性
Reduction
問題Aを問題Bに変換して、問題Bを解いて、問題Aを知る
問題Bの答えがわかれば、問題Aの答えがわかる
例えば、ある問題が決定可能かどうかを調べる時に、すでに判定可能である問題へ帰着できれば、その問題は判定可能だとわかる
問題Aへのどんな入力wも問題Bへの対応する入力f(w)に変換できる
wに対する問題Aの答え(受理or拒否)は、f(w)に対する問題Bの答えと一致する$ \Leftrightarrow A\le B