The complexity of Tarski's fixed point theorem (Q935168)

The Knaster-Tarski theorem says that for every complete lattice \(L\), every order-preserving mapping \(f:L\to L\) has a fixed point. This paper studies the query complexity of this problem. The authors present an algorithm that, for a given complete finite lattice \(L\) and an order-preserving mapping \(f\) of \(L\) given by an oracle, finds a fixed point of \(f\) and requires \(O(| M| \log(\max\{| x| \mid x\in M\}))\) queries to an oracle, where \(M\) is the set of all maximal chains of \(L\). Thus if \(L\) is a finite chain then \(O(\log| L| )\) queries suffice to find a fixed point. On the other hand, if both a finite complete lattice \(L\) and the order-preserving mapping \(f\) are given by oracles, then the expected numbers of queries is \(\Omega (| L| )\) for every random algorithm finding a fixed point of \(f\). Also, every deterministic algorithm constructing a fixed point of \(f\) has to require \(\Omega (| L| )\) queries.