還元可能性 reducibility

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

もう少し厳密に言うと,

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

という条件を満たす関数 $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.





















巡回群 オートマトン 言語 反射律 reflexivity rule 真偽値 truth value 代数的閉体 algebraic closed field