The complexity of Tarski’s fixed point theorem

Abstract: Tarski’s fixed point theorem guarantees the existence of a fixed point of an order-preserving function defined on a nonempty complete lattice [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 when it is given as input and as an oracle. Our algorithm makes queries to when is a total order on . We also prove that when both and are given as oracles, any deterministic or randomized algorithm for finding a fixed point of makes an expected queries for some and . [Copyright &y& Elsevier]