還元可能性 reducibility

問題 $A$ が問題 $B$ に変形でき，問題 $B$ を解くことができれば問題 $A$ も解ける場合，問題 $A$ は問題 $B$ ほど難しくないと言え，これを還元可能性（reducibility）と言います．

もう少し厳密に言うと，

$A,B$ を任意の集合とします．
このとき，

• $h$ は $\Sigma^{*}$ から $\Sigma^{*}$ への関数
• $\forall x \in \Sigma^{*} \bigl[x \in A \leftrightarrow h(x) \in B \bigr]$
• $h$ は計算可能

という条件を満たす関数 $h$ を $A$ から $B$ への帰納的還元といい，

$A$ から $B$ への機能的還元が存在するとき，$A$ から $B$ への帰納的還元が可能といいます．

$A$ から $B$ への帰納的還元が可能であることは，\[A \leq_{m} B\]と表します．ここで，$m$ は recursive many-one reduction の $m$ です．

Mathematics is the language with which God has written the universe.