一次還元

コンピュータサイエンスにおいて、一階還元は、計算複雑性理論における2 つの計算問題間の非常に強力なタイプの還元です。一階還元は、各コンポーネントが一階論理で計算可能な問題のクラスFOに制限される還元です。

であるため、一次簡約は対数空間簡約よりも強い簡約です。 ${\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。