Idioma:

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

Schaefer, Marcus ; Štefankovič, Daniel

Theory of computing systems, 2017-02, Vol.60 (2), p.172-193 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Fixed Points, Nash Equilibria, and the Existential Theory of the Reals
Autor: Schaefer, Marcus ; Štefankovič, Daniel
Assuntos: Algebra ; Analysis ; Boolean ; Complexity ; Computation ; Computer Science ; Equality ; Equilibrium ; Fragmentation ; Game theory ; Geometry ; Graph theory ; Graphs ; Inequalities ; Polynomials ; Robustness ; Studies ; Texts ; Theory of Computation
É parte de: Theory of computing systems, 2017-02, Vol.60 (2), p.172-193
Notas: ObjectType-Article-1
SourceType-Scholarly Journals-1
ObjectType-Feature-2
content type line 23
Descrição: We introduce the complexity class ∃ ℝ based on the existential theory of the reals. We show that the definition of ∃ ℝ 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 ∃ ℝ ; 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 ].
Editor: New York: Springer US
Idioma: Inglês

Voltar para lista de resultados