一次還元

コンピュータサイエンスにおいて、一階縮約とは、計算複雑性理論における2つの計算問題間の非常に強力な縮約の一種である。一階縮約とは、各要素が一階論理で計算可能な問題のクラスFOに限定される縮約である。

であるため、1 次削減は対数空間削減よりも強力な削減です。 ${\displaystyle {\mbox{FO}}\subsetneq {\mbox{L}}}$

多くの重要な計算量クラスは一階還元の下で閉じており、伝統的な完全問題の多くも同様に一階完全である (Immerman 1999, p. 49-50)。例えば、ST連結性はNLに対してFO完全であり、NL はFO還元の下で閉じている (Immerman 1999, p. 51) ( P、NP、その他ほとんどの「行儀の良い」クラスも 同様)。

参考文献

• イマーマン、ニール（1999年）『記述的複雑性』ニューヨーク：シュプリンガー・フェアラーク、ISBN 0-387-98600-6。