The complexity of Tarski's fixed point theorem

@article{citeulike:2929461, abstract = {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,[not precedes, equals]) [B. Knaster, Un th\'{e}or\`{e}me sur les fonctions d'ensembles, Annales de la Soci\'{e}t\'{e} Polonaise de Math\'{e}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,[not precedes, equals]) as input and f as an oracle. Our algorithm makes O(log|L|) queries to f when [not precedes, equals] is a total order on L. We also prove that when both f and (L,[not precedes, equals]) are given as oracles, any deterministic or randomized algorithm for finding a fixed point of f makes an expected [Omega](|L|) queries for some (L,[not precedes, equals]) and f.}, author = {Chang, Ching-Lueh and Lyuu, Yuh-Dauh and Ti, Yen-Wu }, citeulike-article-id = {2929461}, doi = {http://dx.doi.org/10.1016/j.tcs.2008.05.005}, journal = {Theoretical Computer Science}, keywords = {complexity, math, topology}, month = {July}, number = {1-3}, pages = {228--235}, posted-at = {2008-06-26 10:51:13}, priority = {2}, title = {The complexity of Tarski's fixed point theorem}, url = {http://dx.doi.org/10.1016/j.tcs.2008.05.005}, volume = {401}, year = {2008} }

TY - JOUR ID - citeulike:2929461 L3 - citeulike-article-id:2929461 TI - The complexity of Tarski's fixed point theorem JF - Theoretical Computer Science VL - 401 IS - 1-3 SP - 228 EP - 235 N2 - 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,[not precedes, equals]) [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,[not precedes, equals]) as input and f as an oracle. Our algorithm makes O(log|L|) queries to f when [not precedes, equals] is a total order on L. We also prove that when both f and (L,[not precedes, equals]) are given as oracles, any deterministic or randomized algorithm for finding a fixed point of f makes an expected [Omega](|L|) queries for some (L,[not precedes, equals]) and f. KW - complexity KW - math KW - topology AU - Chang, Ching-Lueh AU - Lyuu, Yuh-Dauh AU - Ti, Yen-Wu PY - 2008/07/23/ UR - http://dx.doi.org/10.1016/j.tcs.2008.05.005 ER -