Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

04-11-2015 | Issue 2/2017

Theory of Computing Systems 2/2017

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

Journal:
Theory of Computing Systems > Issue 2/2017
Authors:
Marcus Schaefer, Daniel Štefankovič

Abstract

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].

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literature
About this article

Other articles of this Issue 2/2017

Theory of Computing Systems 2/2017 Go to the issue

Premium Partner

    Image Credits