Fixed Points, Nash Equilibria, and the Existential Theory of the Reals

详细信息    查看全文

• 作者：Marcus Schaefer ; Daniel Štefankovič
• 关键词：Fixed point problems ; Brouwer ; Existential theory of the real numbers ; Nash equilibrium ; Computational complexity
• 刊名：Theory of Computing Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：2
• 页码：172-193
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1433-0490
• 卷排序：60

文摘

We introduce the complexity class \(\exists \mathbb {R}\) based on the existential theory of the reals. We show that the definition of \(\exists \mathbb {R}\) is robust in the sense that even the fragment of the theory expressing solvability of systems of strict polynomial inequalities leads to the same complexity class. Several natural and well-known problems turn out to be complete for \(\exists \mathbb {R}\); here we show that the complexity of decision variants of fixed-point problems, including Nash equilibria, are complete for this class, complementing work by Etessami and Yannakakis [13].