最小不动点
维库，知识与思想的自由文库
在数学分支序理论中，函数的最小不动点(lfp 或 LFP)是按照某种偏序小于等于其他不动点的不动点。
例如，如下实函数的最小不动点
- f(x) = x2
是在实数的通常次序上的 x = 0。有很多不动点定理生成定位最小不动点的算法。最小不动点经常有着任意的不动点所没有的需要的性质。
在数理逻辑中，最小不动点常与做递归定义有关。这导致了描述复杂性的结果，复杂性类 P(在多项式数量的计算时间内可计算的所有问题)精确的等价于可以用带有最小不动点的一阶逻辑所表达的语言的集合。
[编辑] 参见
[编辑] 引用
- Immerman, Neil. Descriptive Complexity, 1999, Springer-Verlag.
- Libkin, Leonid. Elements of Finite Model Theory, 2004, Springer.
