The complexity of Tarski’s fixed point theorem

Tarski’s fixed point theorem guarantees the existence of a fixed point of an order-preserving function f:L→L defined on a nonempty complete lattice (L,⪯) [B. Knaster, Un théorème sur les fonctions d’ensembles, Annales de la Société Polonaise de Mathématique 6 (1928) 133–134; A. Tarski, A lattice theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5 (1955) 285–309]. In this paper, we investigate several algorithmic and complexity-theoretic topics regarding Tarski’s fixed point theorem. In particular, we design an algorithm that finds a fixed point of f when it is given (L,⪯) as input and f as an oracle. Our algorithm makes O(log∣L∣) queries to f when ⪯ is a total order on L. We also prove that when both f and (L,⪯) are given as oracles, any deterministic or randomized algorithm for finding a fixed point of f makes an expected Ω(∣L∣) queries for some (L,⪯) and f.