Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 2/2017

04.11.2015

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

verfasst von: Marcus Schaefer, Daniel Štefankovič

Erschienen in: Theory of Computing Systems | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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].
Vorheriger Artikel Composition Closure of Linear Extended Top-down Tree Transducers
Nächster Artikel Distance Vector-based Advance Reservation with Delay Performance Guarantees

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
When writing formulas in the existential theory of the reals, we will freely use integers and rationals, since these can easily be eliminated without affecting the length of the formula substantially.
 
2
The class of Boolean languages decided by real non-deterministic Turing machines without real constants was introduced under the name \({\text {BP}}(\text {NP}^{0}_{\mathbb {R}})\) by Bürgisser and Cucker [7, Corollary 8.2] who observed that the feasibility problem FEAS (which we will define in Section 4) is complete for that class, based on work by Blum, Shub, and Smale [6]. Since FEAS is also complete for \(\exists _=\mathbb {R}\), as we will show in Theorem 4.1, the two classes coincide.
 
3
The theorem can also be found in [2, Theorem 13.15] though the statement contains a typo in the radius of the ball.
 
4
As far as complexity theory is concerned, the original result by Grigor’ev and Vorobjov would be sufficient, however.
 
5
Using the simplex results to get estimates with explicit constants, was suggested to us by Jiří Matoušek.
 
6
We could allow arbitrary assignments S i : = c, where \(c \in \mathbb {Q}\) or \(c \in [-1,1] \cap \mathbb {Q}\), the following results would still be true if we redefine length in this case to include the number of bits needed to write down any rational constants used. We will see presently that this would not significantly change the model as far as fixed point computations are concerned: allowing division does not yield any additional computational power.
 
7
We refer the reader to their paper—specifically their Section 2.2—for all terminology and definitions related to equilibria used in this section.
 
8
The proof uses Nash equilibria, compare Lemma 5.1 which gets rid of max as well, but adds a fixed point.
 
Literatur
1.
Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987–2006 (2008)MathSciNetCrossRefMATH
2.
Basu, S., Pollack, R., Marie-Françoise, R.: Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. second edition. Springer-Verlag, Berlin (2006)
3.
Basu, S., Marie-Françoise R.: Bounding the radii of balls meeting every connected component of semi-algebraic sets. J. Symbolic Comput. 45(12), 1270–1279 (2010)MathSciNetCrossRefMATH
4.
5.
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer-Verlag, New York (1998). With a foreword by Richard M. KarpCrossRefMATH
6.
Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. (N.S.) 21(1), 1–46 (1989)MathSciNetCrossRefMATH
7.
Bürgisser, P., Cucker, F.: Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. J. Complexity 22(2), 147–191 (2006)MathSciNetCrossRefMATH
8.
Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. J. Comput. System Sci. 58(3), 572–596 (1999)MathSciNetCrossRefMATH
9.
Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC ’88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp 460–469, New York (1988)
10.
Cardinal, J., Kusters, V.: The complexity of simultaneous geometric graph embedding. CoRR, (2013). arXiv: 1302.​7127
11.
12.
Davis, E., Gotts, N., Cohn, A.G.: Constraint networks of topological relations and convexity. Constraints 4(3), 241–280 (1999)MathSciNetCrossRefMATH
13.
Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531–2597 (2010)MathSciNetCrossRefMATH
14.
Grigor’ev, D.Y., Vorobjov, N.N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1-2), 37–64 (1988)MathSciNetCrossRefMATH
15.
Hoon, H.: Comparison of several decision algorithms for the existential theory of the reals. Technical Report 91-41, RISC-Linz, Johannes Kepler University, Linz, Austria (1991)
16.
Jeronimo, G., Perrucci, D.: On the minimum of a positive polynomial over the standard simplex. J. Symbolic Comput. 45(4), 434–442 (2010)MathSciNetCrossRefMATH
17.
Jeronimo, G., Perrucci, D., Tsigaridas, E.: On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications. SIAM J. Optim. 23 (1), 241–255 (2013)MathSciNetCrossRefMATH
18.
19.
Kang, R.J., Müller, T.: Arrangements of pseudocircles and circles. Unpublished manuscript (2013)
20.
21.
Kroening, D., Strichman, O.: Decision procedures. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin (2008). An algorithmic point of view, With a foreword by Randal E. BryantMATH
22.
Jan Kynčl.: Simple realizability of complete abstract topological graphs in P. Discrete Comput. Geom. 45(3), 383–399 (2011)MathSciNetCrossRefMATH
23.
Mishra, B.: Computational real algebraic geometry. In: Handbook of discrete and computational geometry. CRC Press Ser. Discret. Math. Appl., 537–556 (1997). CRC, Boca Raton
24.
Mnëv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and geometry—Rohlin Seminar, vol. 1346 of Lecture Notes in Math., pp. 527–543. Springer, Berlin (1988)
25.
Christos, H.: Papadimitriou. Computational complexity. Addison-Wesley Publishing Company, Reading, MA (1994)
26.
Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3), 498–532 (1994). 31st Annual Symposium on Foundations of Computer Science (FOCS) (St. Louis, MO, 1990)MathSciNetCrossRefMATH
27.
Jürgen Richter-Gebert: Realization spaces of polytopes vol. 1643 of Lecture Notes in Mathematics. Springer-Verlag, Berlin (1996)
28.
Richter-Gebert, J., Ziegler, G.M.: Realization spaces of 4-polytopes are universal. Bull. Am. Math. Soc. (N.S.) 32(4), 403–412 (1995)MathSciNetCrossRefMATH
29.
Schaefer, M.: The real logic of drawing graphs. Unpublished Manuscript
30.
Schaefer, M. Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) : Graph Drawing, vol. 5849 of Lecture Notes in Computer Science, pp 334–344. Springer (2009)
31.
Schaefer, M. Realizability of graphs and linkages. In: Pach, J. (ed.) : Thirty Essays on Geometric Graph Theory, pp 461–482. Springer (2012)
32.
Shor, P.W.: Stretchability of pseudolines is NP-hard. In Applied geometry and discrete mathematics, vol. 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Amer. Math. Soc., Providence, RI (1991)
33.
Sipser, M.: Introduction to the Theory of Computation. Course Technology. 2nd edition (2005)
34.
Tanenbaum, P.J., Goodrich, M.T., Scheinerman, E.R.: Characterization and recognition of point-halfspace and related orders (preliminary version). In: Graph drawing (Princeton, NJ, 1994), vol. 894 of Lecture Notes in Comput. Sci., pp 234–245. Springer, Berlin (1995)
35.
ten Cate, B., Kolaitis, P.G., Othman, W.: Data exchange with arithmetic operations. In: Guerrini, G., Paton, N.W. (eds.) EDBT, pp 537–548. ACM (2013)
36.
37.
Tseitin, G.S.: On the complexity of derivation in propositional logic. In: Wrightson, G., Siekmann, J. (eds.) Automation of Reasoning: Classical Papers on Computational Logic 1967–1970, vol. 2, pp 466–483. Springer (2009)
38.
Vorob’ev, N.N.: Estimates of real roots of a system of algebraic equations. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), vol. 137, pp 7–19 (1984)
39.
Wikipedia: Existential theory of the reals, 2012. (Online; accessed 12-September-2015)
Metadaten
Titel
Fixed Points, Nash Equilibria, and the Existential Theory of the Reals
verfasst von
Marcus Schaefer
Daniel Štefankovič
Publikationsdatum
04.11.2015
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 2/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-015-9662-0

Weitere Artikel der Ausgabe 2/2017

Theory of Computing Systems 2/2017 Zur Ausgabe

OriginalPaper

Sophistication vs Logical Depth

OriginalPaper

Conditional Measure and the Violation of Van Lambalgen’s Theorem for Martin-Löf Randomness

OriginalPaper

Path-Disruption Games: Bribery and a Probabilistic Model

OriginalPaper

Distance Vector-based Advance Reservation with Delay Performance Guarantees

OriginalPaper

The Complexity of Finding Effectors

OriginalPaper

Composition Closure of Linear Extended Top-down Tree Transducers