より弱い還元

ウィキペディア小見出し辞書

より弱い還元

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:07 UTC 版)

「チューリング還元」の記事における「より弱い還元」の解説

チューリング還元よりも弱い還元を作る一般的手法が2つ存在する。第一は神託の回数や方法を制限する手法である。 集合 A が B に多対一還元可能であるとは、要素 n が A に含まれるかどうかを示す関数 f があるとき、B に f(n) が含まれることをいう。このような関数でチューリング還元を生成することもできる（f(n)を計算し、その結果がBに含まれるか神託を訊き、結果を翻訳する）。 真理値表還元では、神託を一度に全部訊き、それらの解にブール関数（真理値表）を適用することで最終的な解が得られる。 第二の手法はチューリング還元を実装するプログラムが使用する計算資源を制限する手法である。これはPのような計算量に関する研究で重要である。集合 A が B に多項式時間チューリング還元可能であるとは、多項式時間で A を B にチューリング還元できることをいう。対数領域還元などの概念も同様である。