{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:34Z","timestamp":1781077714868,"version":"3.54.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,11,4]],"date-time":"2015-11-04T00:00:00Z","timestamp":1446595200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00224-015-9662-0","type":"journal-article","created":{"date-parts":[[2015,11,4]],"date-time":"2015-11-04T04:59:04Z","timestamp":1446613144000},"page":"172-193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":60,"title":["Fixed Points, Nash Equilibria, and the Existential Theory of the Reals"],"prefix":"10.1007","volume":"60","author":[{"given":"Marcus","family":"Schaefer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,11,4]]},"reference":[{"issue":"5","key":"9662_CR1","doi-asserted-by":"crossref","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E Allender","year":"2008","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987\u20132006 (2008)","journal-title":"SIAM J. Comput."},{"key":"9662_CR2","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., Marie-Fran\u00e7oise, R.: Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. second edition. Springer-Verlag, Berlin (2006)","DOI":"10.1007\/3-540-33099-2"},{"issue":"12","key":"9662_CR3","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1016\/j.jsc.2010.06.009","volume":"45","author":"S Basu","year":"2010","unstructured":"Basu, S., Marie-Fran\u00e7oise R.: Bounding the radii of balls meeting every connected component of semi-algebraic sets. J. Symbolic Comput. 45(12), 1270\u20131279 (2010)","journal-title":"J. Symbolic Comput."},{"issue":"5","key":"9662_CR4","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6(5), 443\u2013459 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"9662_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and real computation","author":"L Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer-Verlag, New York (1998). With a foreword by Richard M. Karp"},{"issue":"1","key":"9662_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"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\u201346 (1989)","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"issue":"2","key":"9662_CR7","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.jco.2005.11.001","volume":"22","author":"P B\u00fcrgisser","year":"2006","unstructured":"B\u00fcrgisser, P., Cucker, F.: Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. J. Complexity 22(2), 147\u2013191 (2006)","journal-title":"J. Complexity"},{"issue":"3","key":"9662_CR8","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1006\/jcss.1998.1608","volume":"58","author":"JF Buss","year":"1999","unstructured":"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\u2013596 (1999)","journal-title":"J. Comput. System Sci."},{"key":"9662_CR9","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC \u201988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp 460\u2013469, New York (1988)","DOI":"10.1145\/62212.62257"},{"key":"9662_CR10","unstructured":"Cardinal, J., Kusters, V.: The complexity of simultaneous geometric graph embedding. CoRR, (2013). arXiv: 1302.7127"},{"issue":"3","key":"9662_CR11","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1287\/moor.28.3.424.16397","volume":"28","author":"S Ruchira","year":"2003","unstructured":"Ruchira, S.: Datta. Universality of Nash equilibria. Math. Oper. Res. 28(3), 424\u2013432 (2003)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9662_CR12","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1023\/A:1026401931919","volume":"4","author":"E Davis","year":"1999","unstructured":"Davis, E., Gotts, N., Cohn, A.G.: Constraint networks of topological relations and convexity. Constraints 4(3), 241\u2013280 (1999)","journal-title":"Constraints"},{"issue":"6","key":"9662_CR13","doi-asserted-by":"crossref","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531\u20132597 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"9662_CR14","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"DY Grigor\u2019ev","year":"1988","unstructured":"Grigor\u2019ev, D.Y., Vorobjov, N.N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1-2), 37\u201364 (1988)","journal-title":"J. Symb. Comput."},{"key":"9662_CR15","unstructured":"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)"},{"issue":"4","key":"9662_CR16","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/j.jsc.2010.01.001","volume":"45","author":"G Jeronimo","year":"2010","unstructured":"Jeronimo, G., Perrucci, D.: On the minimum of a positive polynomial over the standard simplex. J. Symbolic Comput. 45(4), 434\u2013442 (2010)","journal-title":"J. Symbolic Comput."},{"issue":"1","key":"9662_CR17","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1137\/110857751","volume":"23","author":"G Jeronimo","year":"2013","unstructured":"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\u2013255 (2013)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"9662_CR18","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1007\/s00454-012-9394-8","volume":"47","author":"JK Ross","year":"2012","unstructured":"Ross, J.K., M\u00fcller, T.: Sphere and dot product representations of graphs. Discrete Comput Geom. 47(3), 548\u2013568 (2012)","journal-title":"Discrete Comput Geom."},{"key":"9662_CR19","doi-asserted-by":"crossref","unstructured":"Kang, R.J., M\u00fcller, T.: Arrangements of pseudocircles and circles. Unpublished manuscript (2013)","DOI":"10.1007\/978-88-7642-475-5_29"},{"issue":"2","key":"9662_CR20","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Combin Theory Ser. B 62(2), 289\u2013315 (1994)","journal-title":"J. Combin Theory Ser. B"},{"key":"9662_CR21","volume-title":"Decision procedures. Texts in Theoretical Computer Science. An EATCS Series","author":"D Kroening","year":"2008","unstructured":"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"},{"issue":"3","key":"9662_CR22","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s00454-010-9320-x","volume":"45","author":"Jan Kyn\u010dl.","year":"2011","unstructured":"Jan Kyn\u010dl.: Simple realizability of complete abstract topological graphs in P. Discrete Comput. Geom. 45(3), 383\u2013399 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"9662_CR23","unstructured":"Mishra, B.: Computational real algebraic geometry. In: Handbook of discrete and computational geometry. CRC Press Ser. Discret. Math. Appl., 537\u2013556 (1997). CRC, Boca Raton"},{"key":"9662_CR24","doi-asserted-by":"crossref","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and geometry\u2014Rohlin Seminar, vol. 1346 of Lecture Notes in Math., pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"key":"9662_CR25","unstructured":"Christos, H.: Papadimitriou. Computational complexity. Addison-Wesley Publishing Company, Reading, MA (1994)"},{"issue":"3","key":"9662_CR26","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3), 498\u2013532 (1994). 31st Annual Symposium on Foundations of Computer Science (FOCS) (St. Louis, MO, 1990)","journal-title":"J. Comput. System Sci."},{"key":"9662_CR27","volume-title":"Realization spaces of polytopes vol. 1643 of Lecture Notes in Mathematics","author":"J\u00fcrgen Richter-Gebert","year":"1996","unstructured":"J\u00fcrgen Richter-Gebert: Realization spaces of polytopes vol. 1643 of Lecture Notes in Mathematics. Springer-Verlag, Berlin (1996)"},{"issue":"4","key":"9662_CR28","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1090\/S0273-0979-1995-00604-X","volume":"32","author":"J Richter-Gebert","year":"1995","unstructured":"Richter-Gebert, J., Ziegler, G.M.: Realization spaces of 4-polytopes are universal. Bull. Am. Math. Soc. (N.S.) 32(4), 403\u2013412 (1995)","journal-title":"Bull. Am. Math. Soc. (N.S.)"},{"key":"9662_CR29","unstructured":"Schaefer, M.: The real logic of drawing graphs. Unpublished Manuscript"},{"key":"9662_CR30","doi-asserted-by":"crossref","unstructured":"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\u2013344. Springer (2009)","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"9662_CR31","doi-asserted-by":"crossref","unstructured":"Schaefer, M. Realizability of graphs and linkages. In: Pach, J. (ed.) : Thirty Essays on Geometric Graph Theory, pp 461\u2013482. Springer (2012)","DOI":"10.1007\/978-1-4614-0110-0_24"},{"key":"9662_CR32","unstructured":"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)"},{"key":"9662_CR33","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Course Technology. 2nd edition (2005)"},{"key":"9662_CR34","doi-asserted-by":"crossref","unstructured":"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\u2013245. Springer, Berlin (1995)","DOI":"10.1007\/3-540-58950-3_375"},{"key":"9662_CR35","doi-asserted-by":"crossref","unstructured":"ten Cate, B., Kolaitis, P.G., Othman, W.: Data exchange with arithmetic operations. In: Guerrini, G., Paton, N.W. (eds.) EDBT, pp 537\u2013548. ACM (2013)","DOI":"10.1145\/2452376.2452439"},{"issue":"2","key":"9662_CR36","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0885-064X(90)90004-W","volume":"6","author":"E Triesch","year":"1990","unstructured":"Triesch, E.: A note on a theorem of Blum, Shub, and Smale. J. Complexity 6 (2), 166\u2013169 (1990)","journal-title":"J. Complexity"},{"key":"9662_CR37","doi-asserted-by":"crossref","unstructured":"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\u20131970, vol. 2, pp 466\u2013483. Springer (2009)","DOI":"10.1007\/978-3-642-81955-1_28"},{"key":"9662_CR38","unstructured":"Vorob\u2019ev, 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\u201319 (1984)"},{"key":"9662_CR39","unstructured":"Wikipedia: Existential theory of the reals, 2012. (Online; accessed 12-September-2015)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9662-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9662-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9662-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9662-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,1]],"date-time":"2019-09-01T07:14:56Z","timestamp":1567322096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9662-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,4]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["9662"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9662-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,4]]}}}