{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T14:13:25Z","timestamp":1776867205601,"version":"3.51.2"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T00:00:00Z","timestamp":1557100800000},"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":["Found Comput Math"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s10208-019-09418-y","type":"journal-article","created":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T16:01:45Z","timestamp":1557244905000},"page":"71-118","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Computing the Homology of Semialgebraic Sets. I: Lax Formulas"],"prefix":"10.1007","volume":"20","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[]},{"given":"Josu\u00e9","family":"Tonelli-Cueto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,6]]},"reference":[{"key":"9418_CR1","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.jco.2016.12.002","volume":"41","author":"D Amelunxen","year":"2017","unstructured":"D.\u00a0Amelunxen and M.\u00a0Lotz. Average-case complexity without the black swans. J. Complexity, 41:82\u2013101, 2017.","journal-title":"J. Complexity"},{"key":"9418_CR2","doi-asserted-by":"crossref","unstructured":"S.\u00a0Basu. On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 408\u2013417. ACM, 1996.","DOI":"10.1145\/237814.237988"},{"issue":"10","key":"9418_CR3","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1016\/j.jsc.2006.07.001","volume":"41","author":"S Basu","year":"2006","unstructured":"S.\u00a0Basu. Computing the first few Betti numbers of semi-algebraic sets in single exponential time. Journal of Symbolic Computation, 41(10):1125\u20131154, 2006.","journal-title":"Journal of Symbolic Computation"},{"key":"9418_CR4","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"S.\u00a0Basu, R.\u00a0Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the Assoc. Comput. Mach., 43:1002\u20131045, 1996.","journal-title":"Journal of the Assoc. Comput. Mach."},{"key":"9418_CR5","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1090\/S0894-0347-99-00311-2","volume":"33","author":"S Basu","year":"1999","unstructured":"S.\u00a0Basu, R.\u00a0Pollack, and M.-F. Roy. Computing roadmaps of semi-algebraic sets on a variety. Journal of the Amer. Math. Soc., 33:55\u201382, 1999.","journal-title":"Journal of the Amer. Math. Soc."},{"issue":"2","key":"9418_CR6","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1090\/S0894-0347-08-00630-9","volume":"22","author":"C Beltr\u00e1n","year":"2009","unstructured":"C.\u00a0Beltr\u00e1n and L.M. Pardo. Smale\u2019s 17th problem: average polynomial time to compute affine and projective solutions. J. Amer. Math. Soc., 22(2):363\u2013385, 2009.","journal-title":"J. Amer. Math. Soc."},{"key":"9418_CR7","unstructured":"R.\u00a0Benedetti and J.-J. Risler. Real algebraic and semi-algebraic sets. Actualit\u00e9s Math\u00e9matiques. [Current Mathematical Topics]. Hermann, Paris, 1990."},{"issue":"1","key":"9418_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"L.\u00a0Blum, M.\u00a0Shub, and S.\u00a0Smale. 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.)"},{"key":"9418_CR9","doi-asserted-by":"crossref","unstructured":"J.\u00a0Bochnak, M.\u00a0Coste, and M.-F. Roy. Real algebraic geometry, volume\u00a036 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3). Springer-Verlag, Berlin, 1998. Translated from the 1987 French original, Revised by the authors.","DOI":"10.1007\/978-3-662-03718-8"},{"issue":"1, Ser. A","key":"9418_CR10","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10107-004-0563-2","volume":"103","author":"H Bosse","year":"2005","unstructured":"H.\u00a0Bosse, M.\u00a0Gr\u00f6tschel, and M.\u00a0Henk. Polynomial inequalities representing polyhedra. Math. Program., 103(1, Ser. A):35\u201344, 2005.","journal-title":"Math. Program."},{"key":"9418_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.2307\/1970177","volume":"75","author":"M Brown","year":"1962","unstructured":"M.\u00a0Brown. Locally flat imbeddings of topological manifolds. Annals of Mathematics, 75:331\u2013341, 1962.","journal-title":"Annals of Mathematics"},{"issue":"2","key":"9418_CR12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10208-007-9006-9","volume":"9","author":"P B\u00fcrgisser","year":"2009","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker. Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math., 9(2):135\u2013170, 2009.","journal-title":"Found. Comput. Math."},{"key":"9418_CR13","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.4007\/annals.2011.174.3.8","volume":"174","author":"P B\u00fcrgisser","year":"2011","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker. On a problem posed by Steve Smale. Annals of Mathematics, 174:1785\u20131836, 2011.","journal-title":"Annals of Mathematics"},{"key":"9418_CR14","doi-asserted-by":"crossref","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker. Condition, volume 349 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 2013.","DOI":"10.1007\/978-3-642-38896-5"},{"issue":"1","key":"9418_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3275242","volume":"66","author":"Peter B\u00fcrgisser","year":"2018","unstructured":"P.\u00a0B\u00fcrgisser, F.\u00a0Cucker, and P.\u00a0Lairez. Computing the homology of basic semialgebraic sets in weak exponential time. J.\u00a0ACM, 66(1):5:1\u20135:30, December 2018.","journal-title":"Journal of the ACM"},{"key":"9418_CR16","doi-asserted-by":"publisher","first-page":"1559","DOI":"10.1090\/S0025-5718-08-02060-7","volume":"77","author":"P B\u00fcrgisser","year":"2008","unstructured":"P.\u00a0B\u00fcrgisser, F.\u00a0Cucker, and M.\u00a0Lotz. The probability that a slightly perturbed numerical analysis problem is difficult. Mathematics of Computation, 77:1559\u20131583, 2008.","journal-title":"Mathematics of Computation"},{"key":"9418_CR17","unstructured":"J.\u00a0Canny. The complexity of robot motion planning, volume 1987 of ACM Doctoral Dissertation Awards. MIT Press, Cambridge, MA, 1988."},{"issue":"5","key":"9418_CR18","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1093\/comjnl\/36.5.504","volume":"36","author":"J Canny","year":"1993","unstructured":"J.\u00a0Canny. Computing roadmaps of general semi-algebraic sets. Comput. J., 36(5):504\u2013514, 1993.","journal-title":"Comput. J."},{"issue":"4","key":"9418_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01614146","volume":"2","author":"J Canny","year":"1992","unstructured":"J.\u00a0Canny, D.Yu. Grigorev, and N.N. Vorobjov. Finding connected components of a semialgebraic set in subexponential time. Appl. Algebra Engrg. Comm. Comput., 2(4):217\u2013238, 1992.","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"key":"9418_CR20","doi-asserted-by":"crossref","unstructured":"F.\u00a0Chazal, D.\u00a0Cohen-Steiner, and A.\u00a0Lieutier. A sampling theory for compact sets in Euclidean space. In Computational geometry (SCG\u201906), pages 319\u2013326. ACM, New York, 2006.","DOI":"10.1145\/1137856.1137904"},{"issue":"4","key":"9418_CR21","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.gmod.2005.01.002","volume":"67","author":"F Chazal","year":"2005","unstructured":"F.\u00a0Chazal and A.\u00a0Lieutier. The \u201c$$\\lambda $$-medial axis\u201d. Graphical Models, 67(4):304 \u2013 331, 2005.","journal-title":"Graphical Models"},{"key":"9418_CR22","doi-asserted-by":"crossref","unstructured":"F.\u00a0Chazal and A.\u00a0Lieutier. Weak feature size and persistant homology: computing homology of solids in $$\\mathbb{R}^n$$ from noisy data samples. In Computational geometry (SCG\u201905), pages 255\u2013262. ACM, New York, 2005.","DOI":"10.1145\/1064092.1064132"},{"key":"9418_CR23","doi-asserted-by":"crossref","unstructured":"G.E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition, pages 134\u2013183. Lecture Notes in Comput. Sci., Vol. 33. Springer, Berlin, 1975.","DOI":"10.1007\/3-540-07407-4_17"},{"key":"9418_CR24","first-page":"180","volume":"27","author":"R Connelly","year":"1971","unstructured":"R.\u00a0Connelly. A New Proof of Brown\u2019s Collaring Theorem. Proc. Am. Math. Soc., 27:180, 1971.","journal-title":"Proc. Am. Math. Soc."},{"key":"9418_CR25","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jcom.1999.0503","volume":"15","author":"F Cucker","year":"1999","unstructured":"F.\u00a0Cucker. Approximate zeros and condition numbers. J. Complexity, 15:214\u2013226, 1999.","journal-title":"J. Complexity"},{"key":"9418_CR26","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.jco.2008.03.001","volume":"24","author":"F Cucker","year":"2008","unstructured":"F.\u00a0Cucker, T.\u00a0Krick, G.\u00a0Malajovich, and M.\u00a0Wschebor. A numerical algorithm for zero counting. I: Complexity and accuracy. J. Complexity, 24:582\u2013605, 2008.","journal-title":"J. Complexity"},{"key":"9418_CR27","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s11784-009-0127-4","volume":"6","author":"F Cucker","year":"2009","unstructured":"F.\u00a0Cucker, T.\u00a0Krick, G.\u00a0Malajovich, and M.\u00a0Wschebor. A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis . J. Fixed Point Theory Appl., 6:285\u2013294, 2009.","journal-title":"J. Fixed Point Theory Appl."},{"key":"9418_CR28","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.aam.2011.07.001","volume":"48","author":"F Cucker","year":"2012","unstructured":"F.\u00a0Cucker, T.\u00a0Krick, G.\u00a0Malajovich, and M.\u00a0Wschebor. A numerical algorithm for zero counting. III: Randomization and condition. Adv. Applied Math., 48:215\u2013248, 2012.","journal-title":"Adv. Applied Math."},{"key":"9418_CR29","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s10208-017-9358-8","volume":"18","author":"F Cucker","year":"2018","unstructured":"F.\u00a0Cucker, T.\u00a0Krick, and M.\u00a0Shub. Computing the homology of real projective sets. Found. Comput. Math., 18:929\u2013970, 2018.","journal-title":"Found. Comput. Math."},{"key":"9418_CR30","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1145\/300515.300519","volume":"46","author":"F Cucker","year":"1999","unstructured":"F.\u00a0Cucker and S.\u00a0Smale. Complexity estimates depending on condition and round-off error. Journal of the Assoc. Comput. Mach., 46:113\u2013184, 1999.","journal-title":"Journal of the Assoc. Comput. Mach."},{"key":"9418_CR31","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1090\/S0025-5718-1988-0929546-7","volume":"50","author":"J Demmel","year":"1988","unstructured":"J.\u00a0Demmel. The probability that a numerical analysis problem is difficult. Math. Comp., 50:449\u2013480, 1988.","journal-title":"Math. Comp."},{"issue":"2","key":"9418_CR32","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1090\/S0002-9947-1983-0688959-3","volume":"276","author":"AH Durfee","year":"1983","unstructured":"A.H. Durfee. Neighborhoods of algebraic sets. Trans. Amer. Math. Soc., 276(2):517\u2013530, 1983.","journal-title":"Trans. Amer. Math. Soc."},{"key":"9418_CR33","volume-title":"Computational topology: An introduction","author":"H Edelsbrunner","year":"2010","unstructured":"H.\u00a0Edelsbrunner and J.L. Harer. Computational topology: An introduction. American Mathematical Society, Providence, RI, 2010."},{"key":"9418_CR34","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1090\/S0002-9947-1959-0110078-1","volume":"93","author":"H Federer","year":"1959","unstructured":"H.\u00a0Federer. Curvature measures. Trans. Amer. Math. Soc., 93:418\u2013491, 1959.","journal-title":"Trans. Amer. Math. Soc."},{"key":"9418_CR35","doi-asserted-by":"crossref","unstructured":"C.G. Gibson, K.\u00a0Wirthm\u00fcller, A.A. du\u00a0Plessis, and E.J.N. Looijenga. Topological stability of smooth mappings. Lecture Notes in Mathematics, Vol. 552. Springer-Verlag, Berlin-New York, 1976.","DOI":"10.1007\/BFb0095244"},{"key":"9418_CR36","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1090\/S0002-9939-1951-0041539-X","volume":"2","author":"HH Goldstine","year":"1951","unstructured":"H.H. Goldstine and J.\u00a0von Neumann. Numerical inverting matrices of high order, II. Proceedings of the Amer. Math. Soc., 2:188\u2013202, 1951.","journal-title":"Proceedings of the Amer. Math. Soc."},{"key":"9418_CR37","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"DYu Grigoriev","year":"1988","unstructured":"D.Yu. Grigoriev. Complexity of deciding Tarski algebra. Journal of Symbolic Computation, 5:65\u2013108, 1988.","journal-title":"Journal of Symbolic Computation"},{"key":"9418_CR38","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"DYu Grigoriev","year":"1988","unstructured":"D.Yu. Grigoriev and N.N. Vorobjov. Solving systems of polynomial inequalities in subexponential time. Journal of Symbolic Computation, 5:37\u201364, 1988.","journal-title":"Journal of Symbolic Computation"},{"key":"9418_CR39","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202001","volume":"2","author":"DYu Grigoriev","year":"1992","unstructured":"D.Yu. Grigoriev and N.N. Vorobjov. Counting connected components of a semialgebraic set in subexponential time. Computational Complexity, 2:133\u2013186, 1992.","journal-title":"Computational Complexity"},{"key":"9418_CR40","volume-title":"Algebraic topology","author":"A Hatcher","year":"2002","unstructured":"A.\u00a0Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002."},{"key":"9418_CR41","doi-asserted-by":"crossref","unstructured":"J.\u00a0Heintz, M.-F. Roy, and P.\u00a0Solerno. Single exponential path finding in semi-algebraic sets II: The general case. In C.L. Bajaj, editor, Algebraic Geometry and its Applications, pages 449\u2013465. Springer-Verlag, 1994.","DOI":"10.1007\/978-1-4612-2628-4_28"},{"key":"9418_CR42","volume-title":"An Introduction to Mathematical Logic","author":"RE Hodel","year":"2013","unstructured":"R.E. Hodel. An Introduction to Mathematical Logic. Dover Publications Inc., Mineola, New York, 2013."},{"key":"9418_CR43","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1006\/jcom.1999.0502","volume":"15","author":"P Koiran","year":"1999","unstructured":"P.\u00a0Koiran. The real dimension problem is $${\\rm NP}_{\\mathbb{R}}$$-complete. J. Complexity, 15:227\u2013238, 1999.","journal-title":"J. Complexity"},{"key":"9418_CR44","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0377-0427(88)90402-5","volume":"22","author":"E Kostlan","year":"1988","unstructured":"E.\u00a0Kostlan. Complexity theory of numerical linear algebra. J. of Computational and Applied Mathematics, 22:219\u2013230, 1988.","journal-title":"J. of Computational and Applied Mathematics"},{"issue":"5","key":"9418_CR45","doi-asserted-by":"publisher","first-page":"1265","DOI":"10.1007\/s10208-016-9319-7","volume":"17","author":"P Lairez","year":"2017","unstructured":"P.\u00a0Lairez. A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time. Found. Comput. Math., 17(5):1265\u20131292, 2017.","journal-title":"Found. Comput. Math."},{"issue":"4","key":"9418_CR46","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1090\/S0273-0979-2012-01383-6","volume":"49","author":"J Mather","year":"2012","unstructured":"J.\u00a0Mather. Notes on topological stability. Bull. Amer. Math. Soc. (N.S.), 49(4):475\u2013506, 2012.","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"9418_CR47","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1090\/S0002-9904-1947-08909-6","volume":"53","author":"J von Neumann","year":"1947","unstructured":"J.\u00a0von Neumann and H.H. Goldstine. Numerical inverting matrices of high order. Bull. Amer. Math. Soc., 53:1021\u20131099, 1947.","journal-title":"Bull. Amer. Math. Soc."},{"issue":"1\u20133","key":"9418_CR48","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00454-008-9053-2","volume":"39","author":"P Niyogi","year":"2008","unstructured":"P.\u00a0Niyogi, S.\u00a0Smale, and S.\u00a0Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39(1-3):419\u2013441, 2008.","journal-title":"Discrete Comput. Geom."},{"key":"9418_CR49","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J Renegar","year":"1992","unstructured":"J.\u00a0Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I. Journal of Symbolic Computation, 13:255\u2013299, 1992.","journal-title":"Part I. Journal of Symbolic Computation"},{"key":"9418_CR50","doi-asserted-by":"crossref","unstructured":"D.J.S. Robinson. A course in the theory of groups, volume\u00a080 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1996.","DOI":"10.1007\/978-1-4419-8594-1"},{"key":"9418_CR51","doi-asserted-by":"crossref","unstructured":"J.J. Rotman. An introduction to algebraic topology, volume 119 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1988.","DOI":"10.1007\/978-1-4612-4576-6"},{"key":"9418_CR52","doi-asserted-by":"publisher","DOI":"10.1007\/b98977","volume-title":"An introduction to homological algebra","author":"JJ Rotman","year":"2009","unstructured":"J.J. Rotman. An introduction to homological algebra. Universitext. Springer, New York, second edition, 2009.","edition":"2"},{"key":"9418_CR53","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0004-3702(88)90053-7","volume":"37","author":"JT Schwartz","year":"1988","unstructured":"J.T. Schwartz and M.\u00a0Sharir. A survey of motion planning and related geometric algorithms. Artificial Intelligence, 37:157\u2013169, 1988.","journal-title":"Artificial Intelligence"},{"key":"9418_CR54","first-page":"459","volume":"6","author":"M Shub","year":"1993","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem I: geometric aspects. Journal of the Amer. Math. Soc., 6:459\u2013501, 1993.","journal-title":"Journal of the Amer. Math. Soc."},{"key":"9418_CR55","doi-asserted-by":"crossref","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem II: volumes and probabilities. In F.\u00a0Eyssette and A.\u00a0Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267\u2013285. Birkh\u00e4user, 1993.","DOI":"10.1007\/978-1-4612-2752-6_19"},{"key":"9418_CR56","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1993.1002","volume":"9","author":"M Shub","year":"1993","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem III: condition number and packing. Journal of Complexity, 9:4\u201314, 1993.","journal-title":"Journal of Complexity"},{"key":"9418_CR57","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(94)90122-8","volume":"133","author":"M Shub","year":"1994","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem V: polynomial time. Theoret. Comp. Sci., 133:141\u2013164, 1994.","journal-title":"Theoret. Comp. Sci."},{"key":"9418_CR58","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0733008","volume":"33","author":"M Shub","year":"1996","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem IV: probability of success; extensions. SIAM J. of Numer. Anal., 33:128\u2013148, 1996.","journal-title":"SIAM J. of Numer. Anal."},{"key":"9418_CR59","doi-asserted-by":"crossref","unstructured":"S.\u00a0Smale. Complexity theory and numerical analysis. In A.\u00a0Iserles, editor, Acta Numerica, pages 523\u2013551. Cambridge University Press, 1997.","DOI":"10.1017\/S0962492900002774"},{"key":"9418_CR60","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF03025291","volume":"20","author":"S Smale","year":"1998","unstructured":"S.\u00a0Smale. Mathematical problems for the next century. Mathematical Intelligencer, 20:7\u201315, 1998.","journal-title":"Mathematical Intelligencer"},{"key":"9418_CR61","volume-title":"Algebraic Topology","author":"E Spanier","year":"1966","unstructured":"E.\u00a0Spanier. Algebraic Topology. McGraw-Hill, New York, 1966."},{"key":"9418_CR62","doi-asserted-by":"crossref","unstructured":"A.\u00a0Tarski. A decision method for elementary algebra and geometry. University of California Press, Berkeley and Los Angeles, Calif., 1951. 2nd ed.","DOI":"10.1525\/9780520348097"},{"key":"9418_CR63","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1090\/S0002-9904-1969-12138-5","volume":"75","author":"R Thom","year":"1969","unstructured":"R.\u00a0Thom. Ensembles et morphismes stratifi\u00e9s. Bull. Amer. Math. Soc., 75:240\u2013284, 1969.","journal-title":"Bull. Amer. Math. Soc."},{"key":"9418_CR64","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1093\/qjmam\/1.1.287","volume":"1","author":"AM Turing","year":"1948","unstructured":"A.M. Turing. Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math., 1:287\u2013308, 1948.","journal-title":"Quart. J. Mech. Appl. Math."},{"key":"9418_CR65","doi-asserted-by":"crossref","unstructured":"H.R. W\u00fcthrich. Ein Entscheidungsverfahren f\u00fcr die Theorie der reell-abgeschlossenen K\u00f6rper. In E.\u00a0Specker and V.\u00a0Strassen, editors, Komplexit\u00e4t von Entscheidungsproblemen, volume\u00a043 of Lect. Notes in Comp. Sci., pages 138\u2013162. Springer-Verlag, 1976.","DOI":"10.1007\/3-540-07805-3_10"},{"key":"9418_CR66","unstructured":"G.M. Ziegler. Lectures on Polytopes. Graduate Texts in Mathematics. Springer New York, 2012."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09418-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-019-09418-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09418-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,17]],"date-time":"2022-09-17T13:21:54Z","timestamp":1663420914000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-019-09418-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,6]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["9418"],"URL":"https:\/\/doi.org\/10.1007\/s10208-019-09418-y","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,6]]},"assertion":[{"value":"7 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}