最小不動點

在數學分支序理論中，函數的最小不動點（英語：Least fixed point）是按照某種偏序小於等於其他不動點的不動點。

例如，如下實函數的最小不動點

$f(x)=x^{2}$

是在實數的通常次序上的 x = 0。有很多不動點定理生成定位最小不動點的算法。最小不動點通常有着合意的性質，是任意的不動點所沒有的。

在數理邏輯中，最小不動點常與做遞歸定義有關。這導致了描述複雜性的結果，複雜性類 P（在多項式數量的計算時間內可計算的所有問題）精確的等價於可以用帶有最小不動點的一階邏輯所表達的語言的集合。

參見

• Kleene不動點定理

引用

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