The complexity of Tarski’s fixed point theorem
Resource
Theoretical Computer Science 401 (1-3): 228-235
Journal
Theoretical Computer Science
Journal Volume
401
Journal Issue
1-3
Pages
228-235
Date Issued
2008
Date
2008
Author(s)
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, {precedes above single-line equals sign}) [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, {precedes above single-line equals sign}) as input and f as an oracle. Our algorithm makes O (log {divides} L {divides}) queries to f when {precedes above single-line equals sign} is a total order on L. We also prove that when both f and (L, {precedes above single-line equals sign}) are given as oracles, any deterministic or randomized algorithm for finding a fixed point of f makes an expected Ω ({divides} L {divides}) queries for some (L, {precedes above single-line equals sign}) and f. © 2008 Elsevier B.V. All rights reserved.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
19.pdf
Size
407.79 KB
Format
Adobe PDF
Checksum
(MD5):a565ab8de02a5a26ac2abc1ff1630301