Optimal bounds on finding fixed points of contraction mappings

The Banach fixed-point theorem states that a contraction mapping on a complete metric space has a unique fixed point. Given an oracle access to a finite metric space (M,d) and a contraction mapping f:M→M on it, we show that the fixed point of f can be found with an expected oracle queries. We also show that every randomized algorithm for finding a fixed point must make an expected oracle queries to (M,d) and f for some finite metric space (M,d) and some contraction mapping f:M→M on it. As a generalization of the Banach fixed-point theorem, the Caristi–Kirk fixed-point theorem gives weaker conditions on (M,d) and f guaranteeing the existence of a fixed point of f. We show that every randomized algorithm that finds a fixed point must make the expected oracle queries to (M,d) and f for some finite metric space (M,d) and some function f:M→M satisfying the conditions of the Caristi–Kirk fixed-point theorem.