2026-07-26T03:43:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10581 2024-03-06T10:46:11Z ddc:004 open_access

Fixed Point Computation Problems and Facets of Complexity (Invited Talk) Yannakakis, Mihalis Fixed Point Polynomial Time Algorithm Computational Complexity Many problems from a wide variety of areas can be formulated mathematically as the problem of computing a fixed point of a suitable given multivariate function. Examples include a variety of problems from game theory, economics, optimization, stochastic analysis, verification, and others. In some problems there is a unique fixed point (for example if the function is a contraction); in others there may be multiple fixed points and any one of them is an acceptable solution; while in other cases the desired object is a specific fixed point (for example the least fixed point or greatest fixed point of a monotone function). In this talk we will discuss several types of fixed point computation problems, their complexity, and some of the common themes that have emerged: classes of problems for which there are efficient algorithms, and other classes for which there seem to be serious obstacles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mihalis Yannakakis 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.5 urn:nbn:de:0030-drops-105812 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.5 eng https://creativecommons.org/licenses/by/3.0/legalcode