最小不動点

最小不動点（さいしょうふどうてん、英: Least fixed point, LFP）は、関数の不動点の中でも、何らかの半順序関係において最も小さい不動点をいう。

例えば、次の実関数

f(x) = x²

の最小不動点は、実数の一般的な順序関係において x = 0 である。様々な不動点定理から最小不動点を求めるアルゴリズムが生み出されている。最小不動点は一般の不動点にはない属性があることが多い。

数理論理学では、最小不動点は何らかの再帰的定義を構築することに関連している。そこから記述計算量の結果として、複雑性クラス P（多項式時間で計算可能な問題のクラス）は一階述語論理に最小不動点を追加したもので表される言語の集合と正確に一致する。

関連項目

• 最大不動点 （あまり使われない）
• クリーネ不動点定理

参考文献

• Immerman, Neil. Descriptive Complexity, 1999, Springer-Verlag.
• Libkin, Leonid. Elements of Finite Model Theory, 2004, Springer.