Least fixed point
From Wikipedia, the free encyclopedia
In order theory, a branch of mathematics, the least fixed point (lfp or LFP) of a function is the fixed point which is less than or equal to all other fixed points, according to some partial order.
For example, the least fixed point of the real function
- f(x) = x2
is x = 0 with the usual order on the real numbers. Many fixed-point theorems yield algorithms for locating the least fixed point. Least fixed points often have desirable properties that arbitrary fixed points do not.
In mathematical logic, the least fixed point is somehow related to making recursive definitions. This leads to the descriptive complexity result that the complexity class P (all problems computable in a polynomial amount of computation time) is exactly equal to the set of languages which can be expressed in a first-order logic with a least fixed point.
[edit] See also
- Greatest fixed point (less commonly used)
- Kleene fixpoint theorem
[edit] References
- Immerman, Neil. Descriptive Complexity, 1999, Springer-Verlag.
- Libkin, Leonid. Elements of Finite Model Theory, 2004, Springer.
