還元可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)
詳細は「還元 (計算複雑性理論)」を参照 チューリング還元可能性以外の還元可能性（reducibility）の研究も盛んである。ポスト（1944）は、真理値表還元可能性を含む強い還元可能性をいくつか提唱した。強い還元可能性を定義する神託付きチューリング機械は、付加されたオラクルがどういうものであろうと全域関数を計算する。弱い還元可能性とは、還元過程が必ずしも全てのオラクルで停止しない（つまり全域関数を計算しない）可能性があるものである。チューリング還元可能性は弱い還元可能性の一種である。 強い還元可能性には、次のものが含まれる。 一対一還元可能性 A が B に一対一還元可能であるとは、全域計算可能な単射 f があり、n が A に属すことと f(n) が B に属すこととが同値になることをいう。 多対一還元可能性 一対一還元可能性とほぼ同じだが、f の単射性を仮定しない。 真理値表還元可能性 A が B に真理値表還元可能であるとは、どんなオラクルに対しても全域関数を計算するような神託機械によってA が B にチューリング還元可能である場合を指す。神託の使用回数を制限したり、神託機械に条件を課すことで、様々な変種が得られる。それらも研究されている。 強い還元可能性に関する主要な研究においては、帰納的可算集合のクラスに対する理論と自然数からなる集合のクラスに対する理論との比較が行われてきた。さらに、各種還元可能性間の関係も研究されている。例えば、チューリング次数は真理値表次数であるか、または無限個の真理値表次数の和集合のどちらかであることが知られている。 チューリング還元可能性よりも弱い還元可能性（つまり、チューリング還元可能性を内包する還元可能性）も研究されている。よく知られている例として、算術的還元可能性と超算術的還元可能性がある。これらの還元可能性は、算術の標準モデルにおける定義可能性と密接に関連している。
※この「還元可能性」の解説は、「再帰理論」の解説の一部です。
「還元可能性」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。
- 還元可能性のページへのリンク
