還元 (計算複雑性理論)
ある決定問題が決定不可能であることを示すために、計算可能関数を使ってそれを既に決定不可能と分かっている決定問題に変換する。特に、ある問題が決定不能であることを示すために、チューリングマシンの停止問題がその問題に還元可能であることを示すという手法がよく使われる。
複雑性クラス P、NP、PSPACE は多項式時間還元において閉じている。
複雑性クラス L、NL、P、NP、PSPACE は対数空間還元において閉じている。