×

Fixed points, Nash equilibria, and the existential theory of the reals. (English) Zbl 1362.68088

Summary: 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 K. Etessami and M. Yannakakis [SIAM J. Comput. 39, No. 6, 2531–2597 (2010; Zbl 1204.91003)].

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03B25 Decidability of theories and sets of sentences
03C07 Basic properties of first-order languages and structures
14P10 Semialgebraic sets and related spaces
54H25 Fixed-point and coincidence theorems (topological aspects)
91A10 Noncooperative games
91A44 Games involving topology, set theory, or logic

Citations:

Zbl 1204.91003
PDFBibTeX XMLCite
Full Text: DOI

References:

[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) · Zbl 1191.68329 · doi:10.1137/070697926
[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) · Zbl 1102.14041
[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) · Zbl 1200.14107 · doi:10.1016/j.jsc.2010.06.009
[4] Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6(5), 443-459 (1991) · Zbl 0765.68202 · doi:10.1007/BF02574701
[5] Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer-Verlag, New York (1998). With a foreword by Richard M. Karp · Zbl 0872.68036 · doi:10.1007/978-1-4612-0701-6
[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) · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[7] Bürgisser, P., Cucker, F.: Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. J. Complexity 22(2), 147-191 (2006) · Zbl 1149.68029 · doi:10.1016/j.jco.2005.11.001
[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) · Zbl 0941.68059 · doi:10.1006/jcss.1998.1608
[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 · Zbl 1311.05128
[11] Ruchira, S.: Datta. Universality of Nash equilibria. Math. Oper. Res. 28(3), 424-432 (2003) · Zbl 1082.91010 · doi:10.1287/moor.28.3.424.16397
[12] Davis, E., Gotts, N., Cohn, A.G.: Constraint networks of topological relations and convexity. Constraints 4(3), 241-280 (1999) · Zbl 0946.68082 · doi:10.1023/A:1026401931919
[13] Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531-2597 (2010) · Zbl 1204.91003 · doi:10.1137/080720826
[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) · Zbl 0662.12001 · doi:10.1016/S0747-7171(88)80005-1
[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) · Zbl 1214.05013
[16] Jeronimo, G., Perrucci, D.: On the minimum of a positive polynomial over the standard simplex. J. Symbolic Comput. 45(4), 434-442 (2010) · Zbl 1239.90086 · doi:10.1016/j.jsc.2010.01.001
[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) · Zbl 1272.14042 · doi:10.1137/110857751
[18] Ross, J.K., Müller, T.: Sphere and dot product representations of graphs. Discrete Comput Geom. 47(3), 548-568 (2012) · Zbl 1238.05180 · doi:10.1007/s00454-012-9394-8
[19] Kang, R.J., Müller, T.: Arrangements of pseudocircles and circles. Unpublished manuscript (2013) · Zbl 1292.52026
[20] Kratochvíl, J., Matoušek, J.: Intersection graphs of segments. J. Combin Theory Ser. B 62(2), 289-315 (1994) · Zbl 0808.68075 · doi:10.1006/jctb.1994.1071
[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. Bryant · Zbl 1149.68071
[22] Jan Kynčl.: Simple realizability of complete abstract topological graphs in P. Discrete Comput. Geom. 45(3), 383-399 (2011) · Zbl 1214.05013 · doi:10.1007/s00454-010-9320-x
[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 · Zbl 0940.68184
[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) · Zbl 0667.52006
[25] Christos, H.: Papadimitriou. Computational complexity. Addison-Wesley Publishing Company, Reading, MA (1994) · Zbl 1238.05180
[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) · Zbl 0806.68048 · doi:10.1016/S0022-0000(05)80063-7
[27] Jürgen Richter-Gebert: Realization spaces of polytopes vol. 1643 of Lecture Notes in Mathematics. Springer-Verlag, Berlin (1996) · Zbl 0866.52009
[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) · Zbl 0853.52012 · doi:10.1090/S0273-0979-1995-00604-X
[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) · Zbl 1284.68305
[31] Schaefer, M. Realizability of graphs and linkages. In: Pach, J. (ed.) : Thirty Essays on Geometric Graph Theory, pp 461-482. Springer (2012) · Zbl 1272.05135
[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) · Zbl 0751.05023
[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) · Zbl 0941.68059
[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) · Zbl 1200.14107
[36] Triesch, E.: A note on a theorem of Blum, Shub, and Smale. J. Complexity 6 (2), 166-169 (1990) · Zbl 0695.03020 · doi:10.1016/0885-064X(90)90004-W
[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) · Zbl 1238.05180
[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) · Zbl 0546.65027
[39] Wikipedia: Existential theory of the reals, 2012. (Online; accessed 12-September-2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.