資源制限つきの多対一還元

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

資源制限つきの多対一還元

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

「多対一還元」の記事における「資源制限つきの多対一還元」の解説

多対一還元は計算資源の制限と合わせて論じられることが多い。例えばその還元関数が多項式時間や対数領域で計算可能か、などである。詳しくは多項式時間還元と対数領域還元を参照のこと。 決定問題 A と B があり、また B を解けるアルゴリズム N があるとする。このとき、A を B に多対一還元できるなら、N を応用して A を解けるが、この時のコストは次の通りとなる。 N を実行するのに必要な時間＋還元に必要な時間 N を実行するのに必要な最大領域＋還元に必要な領域 何らかの言語（または、自然数の集合）のクラス C について、C に含まれない言語を C に含まれる言語へ多対一還元できないとき、C は「多対一還元の下で閉じている」と言う。もし C が多対一還元の下で閉じているなら、C に含まれる問題を他の問題に多対一還元できた場合、その還元もとの問題も C に含まれることが言える。多対一還元が便利なのは、よく知られている計算量の殆どは何らかの多対一還元の下で閉じているからである。このようなクラスとしては P、NP、L、NL、co-NP、PSPACE、EXPTIMEなどがあり、他にも多数存在する。しかしながら、これらのクラスも任意の多対一還元の下で閉じている訳ではない。