文章基本信息

标题：Fixed Point Computation Problems and Facets of Complexity (Invited Talk)
本地全文：下载
作者：Mihalis Yannakakis
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-1
DOI：10.4230/LIPIcs.ICALP.2019.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Fixed Point; Polynomial Time Algorithm; Computational Complexity