{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:43Z","timestamp":1778498023608,"version":"3.51.4"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s00224-023-10151-x","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T09:14:42Z","timestamp":1702372482000},"page":"195-226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Beyond the Existential Theory of the Reals"],"prefix":"10.1007","volume":"68","author":[{"given":"Marcus","family":"Schaefer","sequence":"first","affiliation":[]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"10151_CR1","doi-asserted-by":"publisher","unstructured":"Jungeblut, P., Kleist, L., Miltzow, T.: The complexity of the Hausdorff distance. In: 38th International Symposium on Computational Geometry. LIPIcs. Leibniz Int. Proc. Inform., vol. 224, pp. 48\u201317. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2022). https:\/\/doi.org\/10.4230\/lipics.socg.2022.48","DOI":"10.4230\/lipics.socg.2022.48"},{"key":"10151_CR2","doi-asserted-by":"publisher","unstructured":"D\u2019Costa, J., Lefaucheux, E., Neumann, E., Ouaknine, J., Worrell, J.: On the complexity of the escape problem for linear dynamical systems over compact semialgebraic sets. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science. LIPIcs. Leibniz Int. Proc. Inform., vol. 202, pp. 33\u201321. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.33","DOI":"10.4230\/LIPIcs.MFCS.2021.33"},{"key":"10151_CR3","doi-asserted-by":"publisher","unstructured":"Dobbins, M.G., Kleist, L., Miltzow, T., Rz\u0105\u017cewski, P.: $$\\forall \\exists \\mathbb{R}$$-completeness and area-universality. In: Graph-theoretic Concepts in Computer Science. Lecture Notes in Comput. Sci., vol. 11159, pp. 164\u2013175. Springer, ??? (2018). https:\/\/doi.org\/10.1007\/978-3-030-00256-5_14","DOI":"10.1007\/978-3-030-00256-5_14"},{"key":"10151_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00381-0","author":"MG Dobbins","year":"2022","unstructured":"Dobbins, M.G., Kleist, L., Miltzow, T., Rz\u0105\u017cewski, P.: Completeness for the complexity class $$\\forall \\exists \\mathbb{R} $$ and area-universality. Discrete Comput. Geom. (2022). https:\/\/doi.org\/10.1007\/s00454-022-00381-0","journal-title":"Discrete Comput. Geom."},{"key":"10151_CR5","doi-asserted-by":"publisher","unstructured":"Blanc, M., Hansen, K.A.: Computational complexity of multi-player evolutionarily stable strategies. ArXiv e-prints. (2022) https:\/\/doi.org\/10.48550\/ARXIV.2203.07407","DOI":"10.48550\/ARXIV.2203.07407"},{"issue":"2","key":"10151_CR6","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/s00224-015-9662-0","volume":"60","author":"M Schaefer","year":"2017","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst. 60(2), 172\u2013193 (2017). https:\/\/doi.org\/10.1007\/s00224-015-9662-0","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"10151_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10208-007-9006-9","volume":"9","author":"P B\u00fcrgisser","year":"2009","unstructured":"B\u00fcrgisser, P., Cucker, F.: Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math. 9(2), 135\u2013170 (2009). https:\/\/doi.org\/10.1007\/s10208-007-9006-9","journal-title":"Found. Comput. Math."},{"key":"10151_CR8","first-page":"60","volume-title":"A Decision Method for Elementary Algebra And Geometry","author":"A Tarski","year":"1948","unstructured":"Tarski, A.: A Decision Method for Elementary Algebra And Geometry, p. 60. The Rand Corporation, Santa Monica, Calif (1948)"},{"key":"10151_CR9","doi-asserted-by":"publisher","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, 2nd edn. Algorithms and Computation in Mathematics, vol. 10, p. 662. Springer, Berlin (2006). https:\/\/doi.org\/10.1007\/3-540-33099-2","DOI":"10.1007\/3-540-33099-2"},{"issue":"1","key":"10151_CR10","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/3486220","volume":"69","author":"M Abrahamsen","year":"2022","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R} $$-complete. J. ACM. 69(1), 4\u201370 (2022). https:\/\/doi.org\/10.1145\/3486220","journal-title":"J. ACM."},{"key":"10151_CR11","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M.: Covering polygons is even harder. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2021, pp. 375\u2013386. IEEE Computer Soc., Los Alamitos, CA (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00045","DOI":"10.1109\/FOCS52979.2021.00045"},{"issue":"7","key":"10151_CR12","doi-asserted-by":"publisher","first-page":"565","DOI":"10.7155\/jgaa.00634","volume":"27","author":"M Schaefer","year":"2023","unstructured":"Schaefer, M.: The complexity of angular resolution. J. Graph Algorithms Appl. 27(7), 565\u2013580 (2023). https:\/\/doi.org\/10.7155\/jgaa.00634","journal-title":"J. Graph Algorithms Appl."},{"key":"10151_CR13","doi-asserted-by":"publisher","unstructured":"Miltzow, T., Schmiermann, R.F.: On classifying continuous constraint satisfaction problems. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2021, pp. 781\u2013791. IEEE Computer Soc., Los Alamitos, CA (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00081","DOI":"10.1109\/FOCS52979.2021.00081"},{"issue":"3","key":"10151_CR14","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s00224-022-10080-1","volume":"66","author":"MLT Berthelsen","year":"2022","unstructured":"Berthelsen, M.L.T., Hansen, K.A.: On the computational complexity of decision problems about multi-player Nash equilibria. Theory Comput. Syst. 66(3), 519\u2013545 (2022). https:\/\/doi.org\/10.1007\/s00224-022-10080-1","journal-title":"Theory Comput. Syst."},{"key":"10151_CR15","doi-asserted-by":"publisher","unstructured":"Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., Weber, S.: Training fully connected neural networks is $$\\exists \\mathbb{R}$$-complete. ArXiv e-prints. (2022) https:\/\/doi.org\/10.48550\/arXiv.2204.01368","DOI":"10.48550\/arXiv.2204.01368"},{"key":"10151_CR16","unstructured":"Matou\u0161ek, J.: Intersection graphs of segments and $$\\exists \\mathbb{R}$$. ArXiv e-prints. (2014). arXiv:1406.2636"},{"key":"10151_CR17","unstructured":"Wikipedia: Existential theory of the reals. (Online; accessed 6-June-2022) (2012). http:\/\/en.wikipedia.org\/wiki\/Existential_theory_of_the_reals"},{"issue":"5","key":"10151_CR18","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/BF02574701","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"10151_CR19","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1006\/jctb.1994.1071","journal-title":"J. Combin. Theory Ser. B."},{"key":"10151_CR20","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. Lecture Notes in Math., vol. 1346, pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"key":"10151_CR21","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied Geometry and Discrete Mathematics. DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, pp. 531\u2013554. Amer. Math. Soc., Providence, RI (1991). https:\/\/doi.org\/10.1090\/dimacs\/004\/41","DOI":"10.1090\/dimacs\/004\/41"},{"issue":"3","key":"10151_CR22","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s00037-015-0105-8","volume":"24","author":"A Shpilka","year":"2015","unstructured":"Shpilka, A., Volkovich, I.: Read-once polynomial identity testing. Comput. Complexity. 24(3), 477\u2013532 (2015). https:\/\/doi.org\/10.1007\/s00037-015-0105-8","journal-title":"Comput. Complexity."},{"issue":"3","key":"10151_CR23","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(85)90076-6","volume":"20","author":"ED Sontag","year":"1985","unstructured":"Sontag, E.D.: Real addition and the polynomial hierarchy. Inform. Process. Lett. 20(3), 115\u2013120 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90076-6","journal-title":"Inform. Process. Lett."},{"key":"10151_CR24","doi-asserted-by":"publisher","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation, p. 453. Springer, New York (1998). https:\/\/doi.org\/10.1007\/978-1-4612-0701-6","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"10151_CR25","doi-asserted-by":"publisher","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) https:\/\/doi.org\/10.1090\/S0273-0979-1989-15750-9","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"10151_CR26","doi-asserted-by":"publisher","unstructured":"B\u00fcrgisser, P., Cucker, F.: Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. J. Complexity. 22(2), 147\u2013191 (2006) https:\/\/doi.org\/10.1145\/1007352.1007425","DOI":"10.1145\/1007352.1007425"},{"issue":"4","key":"10151_CR27","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10208-010-9062-4","volume":"10","author":"S Basu","year":"2010","unstructured":"Basu, S., Zell, T.: Polynomial hierarchy, Betti numbers, and a real analogue of Toda\u2019s theorem. Found. Comput. Math. 10(4), 429\u2013454 (2010). https:\/\/doi.org\/10.1007\/s10208-010-9062-4","journal-title":"Found. Comput. Math."},{"issue":"1","key":"10151_CR28","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01810850","volume":"2","author":"P Solern\u00f3","year":"1991","unstructured":"Solern\u00f3, P.: Effective \u0141ojasiewicz inequalities in semialgebraic geometry. Appl. Algebra Engrg. Comm. Comput. 2(1), 2\u201314 (1991). https:\/\/doi.org\/10.1007\/BF01810850","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"key":"10151_CR29","doi-asserted-by":"publisher","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. J. Symbolic Comput. 13(3), 255\u2013299 (1992) https:\/\/doi.org\/10.1016\/S0747-7171(10)80003-3","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"10151_CR30","doi-asserted-by":"publisher","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. II. The general decision problem. Preliminaries for quantifier elimination. J. Symbolic Comput. 13(3), 301\u2013327 (1992) https:\/\/doi.org\/10.1016\/S0747-7171(10)80004-5","DOI":"10.1016\/S0747-7171(10)80004-5"},{"issue":"3","key":"10151_CR31","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/S0747-7171(10)80005-7","volume":"13","author":"J Renegar","year":"1992","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. III. Quantifier elimination. J. Symbolic Comput. 13(3), 329\u2013352 (1992). https:\/\/doi.org\/10.1016\/S0747-7171(10)80005-7","journal-title":"III. Quantifier elimination. J. Symbolic Comput."},{"issue":"4","key":"10151_CR32","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.jsc.2010.01.001","journal-title":"J. Symbolic Comput."},{"key":"10151_CR33","doi-asserted-by":"publisher","unstructured":"Ouaknine, J., Worrell, J.: Ultimate positivity is decidable for simple linear recurrence sequences. ArXiv e-prints. (2017) https:\/\/doi.org\/10.48550\/arXiv.1309.1914, arXiv:1309.1914","DOI":"10.48550\/arXiv.1309.1914"},{"key":"10151_CR34","doi-asserted-by":"publisher","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Thirty Essays on Geometric Graph Theory, pp. 461\u2013482. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-0110-0_24","DOI":"10.1007\/978-1-4614-0110-0_24"},{"key":"10151_CR35","doi-asserted-by":"publisher","unstructured":"Cucker, F., Rossell\u00f3, F.: On the complexity of some problems for the Blum, Shub & Smale model. In: LATIN \u201992 (S\u00e3o Paulo, 1992). Lecture Notes in Comput. Sci., vol. 583, pp. 117\u2013129. Springer, ??? (1992). https:\/\/doi.org\/10.1007\/BFb0023823","DOI":"10.1007\/BFb0023823"},{"key":"10151_CR36","doi-asserted-by":"publisher","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization, p. 716. Cambridge University Press, Cambridge (2004). https:\/\/doi.org\/10.1017\/CBO9780511804441","DOI":"10.1017\/CBO9780511804441"},{"issue":"2","key":"10151_CR37","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1006\/jcom.1999.0502","volume":"15","author":"P Koiran","year":"1999","unstructured":"Koiran, P.: The real dimension problem is $${\\rm NP}_{\\mathbb{R} }$$-complete. J. Complexity. 15(2), 227\u2013238 (1999). https:\/\/doi.org\/10.1006\/jcom.1999.0502","journal-title":"J. Complexity."},{"issue":"1\u20134","key":"10151_CR38","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10472-005-0432-6","volume":"43","author":"S Szeider","year":"2005","unstructured":"Szeider, S.: Generalizations of matched CNF formulas. Ann. Math. Artif. Intell. 43(1\u20134), 223\u2013238 (2005). https:\/\/doi.org\/10.1007\/s10472-005-0432-6","journal-title":"Ann. Math. Artif. Intell."},{"key":"10151_CR39","doi-asserted-by":"publisher","unstructured":"Le, H.P., Safey El\u00a0Din, M., Wolff, T.: Computing the real isolated points of an algebraic hypersurface. In: ISSAC\u201920\u2014Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, pp. 297\u2013304. ACM, New York (2020). https:\/\/doi.org\/10.1145\/3373207.3404049","DOI":"10.1145\/3373207.3404049"},{"key":"10151_CR40","doi-asserted-by":"publisher","unstructured":"Lov\u00e1sz, L.: Semidefinite programs and combinatorial optimization. In: Recent Advances in Algorithms and Combinatorics. CMS Books Math.\/Ouvrages Math. SMC, vol. 11, pp. 137\u2013194. Springer,??? (2003). https:\/\/doi.org\/10.1007\/0-387-22444-0_6","DOI":"10.1007\/0-387-22444-0_6"},{"key":"10151_CR41","doi-asserted-by":"publisher","unstructured":"Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Programming. 77(2, Ser. B), 129\u2013162 (1997) https:\/\/doi.org\/10.1016\/S0025-5610(96)00082-2","DOI":"10.1016\/S0025-5610(96)00082-2"},{"key":"10151_CR42","doi-asserted-by":"publisher","unstructured":"Goemans, M.X.: Semidefinite programming and combinatorial optimization. In: Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), vol. Extra Vol. III, pp. 657\u2013666 (1998). https:\/\/doi.org\/10.4171\/DMS\/1-3\/63","DOI":"10.4171\/DMS\/1-3\/63"},{"issue":"5","key":"10151_CR43","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E Allender","year":"2009","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 (2009). https:\/\/doi.org\/10.1137\/070697926","journal-title":"SIAM J. Comput."},{"key":"10151_CR44","doi-asserted-by":"publisher","unstructured":"Erickson, J., Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp. 1022\u20131033. IEEE Computer Soc., Los Alamitos, CA (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00099","DOI":"10.1109\/FOCS46700.2020.00099"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10151-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10151-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10151-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T04:02:15Z","timestamp":1712289735000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10151-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10151"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10151-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"12 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}