|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 多 ： [た] 1. (n,pref) multi- ・ 対 ： [つい] 【名詞】 1. pair 2. couple 3. set ・ 一 ： [いち] 1. (num) one ・ 還元 ： [かんげん] 1. (n,vs) resolution 2. reduction 3. return to origins ・ 元 ： [げん, もと, がん] 1. (n,n-suf,n-t) (1) origin 2. basis 3. foundation 4. (2) former
多対一還元（たたいいちかんげん、many-one reduction）とは、計算理論と計算量理論におけるある種の還元操作の名前。何らかの決定問題を他の決定問題に変換する働きを持つ。 多対一還元はチューリング還元の特殊ケースであり、チューリング還元よりも弱い（多対一還元可能であるという主張はチューリング還元可能よりも強い）。多対一還元においては、オラクルの使用（神託機械参照）は一度だけ、そして最後にだけ許される。 多対一還元は1944年、エミール・ポストによって初めて導入された。1956年、Norman Shapiro は同じ概念を ''strong reducibility'' という名前で適用した。 ==定義== ===形式言語=== ''A'' と ''B'' をそれぞれアルファベットの集合 Σ と Γの上で書かれた形式言語だとしよう。''A'' から ''B'' への多対一還元とは、次の性質を満たすような全体計算可能関数 ''f'' : Σ * → Γ * を指す。性質：「個々の単語 ''w'' が ''A'' の中にある必要十分条件が、『''f''(''w'') が ''B'' の中にあること』（即ち、）である」。 もしそのような関数 ''f'' が存在するなら、''A'' は ''B'' に多対一還元可能またはm-還元可能であると言い、次のように書く。 : もし単射な多対一還元があるなら、''A'' は ''B'' に1-還元可能または一対一還元可能であると言い、次のように書く。 : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「多対一還元」の詳細全文を読む スポンサード リンク
|