Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 2/2017

04-11-2015

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

Authors: Marcus Schaefer, Daniel Štefankovič

Published in: Theory of Computing Systems | Issue 2/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

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].
previous article Composition Closure of Linear Extended Top-down Tree Transducers
next article Distance Vector-based Advance Reservation with Delay Performance Guarantees

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Footnotes
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.
 
Literature
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.
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.
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)
Metadata
Title
Fixed Points, Nash Equilibria, and the Existential Theory of the Reals
Authors
Marcus Schaefer
Daniel Štefankovič
Publication date
04-11-2015
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 2/2017
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-015-9662-0

Other articles of this Issue 2/2017

Theory of Computing Systems 2/2017 Go to the issue

OriginalPaper

The Complexity of Finding Effectors

OriginalPaper

Path-Disruption Games: Bribery and a Probabilistic Model

OriginalPaper

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

OriginalPaper

The Behavior of Clique-Width under Graph Operations and Graph Transformations

OriginalPaper

Sophistication vs Logical Depth

OriginalPaper

A Difference in Complexity Between Recursion and Tail Recursion

Premium Partner

    Image Credits