最小不动点

在数学分支序理论中，函数的最小不动点（英語：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.