{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:12:17Z","timestamp":1778497937401,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,2,19]],"date-time":"2010-02-19T00:00:00Z","timestamp":1266537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s10208-010-9062-4","type":"journal-article","created":{"date-parts":[[2010,2,18]],"date-time":"2010-02-18T10:15:11Z","timestamp":1266488111000},"page":"429-454","source":"Crossref","is-referenced-by-count":12,"title":["Polynomial Hierarchy, Betti Numbers, and\u00a0a\u00a0Real\u00a0Analogue of Toda\u2019s Theorem"],"prefix":"10.1007","volume":"10","author":[{"given":"Saugata","family":"Basu","sequence":"first","affiliation":[]},{"given":"Thierry","family":"Zell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,2,19]]},"reference":[{"issue":"1","key":"9062_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009443","volume":"22","author":"S. Basu","year":"1999","unstructured":"S. Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Discrete Comput. Geom. 22(1), 1\u201318 (1999).","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9062_CR2","doi-asserted-by":"crossref","first-page":"1125","DOI":"10.1016\/j.jsc.2006.07.001","volume":"41","author":"S. Basu","year":"2006","unstructured":"S. Basu, Computing the first few Betti numbers of semi-algebraic sets in single exponential time, J.\u00a0Symb. Comput. 41(1), 1125\u20131154 (2006). MR 2262087 (2007k:14120).","journal-title":"J.\u00a0Symb. Comput."},{"key":"9062_CR3","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/conm\/453\/08799","volume-title":"Surveys on Discrete and Computational Geometry: Twenty Years Later","author":"S. Basu","year":"2008","unstructured":"S. Basu, Algorithmic semi-algebraic geometry and topology\u2014recent progress and open problems, in Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary Mathematics, vol. 453 (American Mathematical Society, Providence, 2008), pp. 139\u2013212."},{"issue":"6","key":"9062_CR4","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S. Basu","year":"1996","unstructured":"S. Basu, R. Pollack, M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM 43(6), 1002\u20131045 (1996). MR 98c:03077.","journal-title":"J. ACM"},{"issue":"1","key":"9062_CR5","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1090\/S0894-0347-99-00311-2","volume":"13","author":"S. Basu","year":"2000","unstructured":"S. Basu, R. Pollack, M.-F. Roy, Computing roadmaps of semi-algebraic sets on a variety, J. Am. Math. Soc. 13(1), 55\u201382 (2000). MR 1685780 (2000h:14048).","journal-title":"J. Am. Math. Soc."},{"key":"9062_CR6","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S. Basu","year":"2006","unstructured":"S. Basu, R. Pollack, M.-F. Roy, Algorithms in Real Algebraic Geometry, 2nd edn., Algorithms and Computation in Mathematics, vol. 10 (Springer, Berlin, 2006). MR 1998147 (2004g:14064).","edition":"2"},{"issue":"1","key":"9062_CR7","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10208-007-9001-1","volume":"8","author":"S. Basu","year":"2008","unstructured":"S. Basu, R. Pollack, M.-F. Roy, Computing the first Betti number of a semi-algebraic set, Found. Comput. Math. 8(1), 97\u2013136 (2008).","journal-title":"Found. Comput. Math."},{"issue":"5","key":"9062_CR8","doi-asserted-by":"crossref","first-page":"1877\u20131899","DOI":"10.1090\/S0002-9947-04-03496-8","volume":"357","author":"A. Bjorner","year":"2004","unstructured":"A. Bjorner, M.L. Wachs, V. Welker, Poset fiber theorems, Trans. Am. Math. Soc. 357(5), 1877\u20131899 (2004).","journal-title":"Trans. Am. Math. Soc."},{"key":"9062_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1998). With a foreword by Richard M. Karp. MR 99a:68070."},{"issue":"1","key":"9062_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Am. Math. Soc. (NS) 21(1), 1\u201346 (1989). MR 90a:68022.","journal-title":"Bull. Am. Math. Soc. (NS)"},{"key":"9062_CR11","unstructured":"J. Bochnak, M. Coste, M.-F. Roy, G\u00e9om\u00e9trie Alg\u00e9brique R\u00e9elle (second edition in English: Real Algebraic Geometry), Ergebnisse der Mathematik und ihrer Grenzgebiete (Results in Mathematics and Related Areas), vol. 12(36) (Springer, Berlin, 1987 (1998)). MR 949442 (90b:14030)."},{"key":"9062_CR12","unstructured":"P. B\u00fcrgisser, F. Cucker, Variations by complexity theorists on three themes of Euler, B\u00e9zout, Betti, and Poincar\u00e9, in Complexity of Computations and Proofs, Quad. Mat., vol.\u00a013 (Dept. Math., Seconda Univ. Napoli, Caserta, 2004), pp.\u00a073\u2013151. MR 2131406 (2006c:68053)."},{"issue":"2","key":"9062_CR13","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.jco.2005.11.001","volume":"22","author":"P. B\u00fcrgisser","year":"2006","unstructured":"P. B\u00fcrgisser, F. Cucker, Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets, J. Complex. 22(2), 147\u2013191 (2006). MR 2200367 (2007b:68059).","journal-title":"J. Complex."},{"issue":"4","key":"9062_CR14","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s10208-005-0146-x","volume":"5","author":"P. B\u00fcrgisser","year":"2005","unstructured":"P. B\u00fcrgisser, F. Cucker, M. Lotz, Counting complexity classes for numeric computations. III. Complex projective sets, Found. Comput. Math. 5(4), 351\u2013387 (2005). MR 2189543 (2006h:68039).","journal-title":"Found. Comput. Math."},{"key":"9062_CR15","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1093\/comjnl\/36.5.504","volume":"36","author":"J. Canny","year":"1993","unstructured":"J. Canny, Computing road maps in general semi-algebraic sets, Comput. J. 36, 504\u2013514 (1993).","journal-title":"Comput. J."},{"issue":"1","key":"9062_CR16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s00222-008-0114-1","volume":"173","author":"R. Cluckers","year":"2008","unstructured":"R. Cluckers, F. Loeser, Constructible motivic functions and motivic integration, Invent. Math. 173(1), 23\u2013121 (2008). MR 2403394 (2009g:14018).","journal-title":"Invent. Math."},{"key":"9062_CR17","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0074551","volume-title":"Locally Semialgebraic Spaces","author":"H. Delfs","year":"1985","unstructured":"H. Delfs, M. Knebusch, Locally Semialgebraic Spaces, Lecture Notes in Mathematics, vol. 1173 (Springer, Berlin, 1985). MR 819737 (87h:14019)."},{"key":"9062_CR18","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02684373","volume":"43","author":"P. Deligne","year":"1974","unstructured":"P. Deligne, La conjecture de\u00a0Weil. I, Inst. Hautes \u00c9tudes Sci. Publ. Math. 43, 273\u2013307 (1974). MR 0340258 (49 #5013).","journal-title":"Inst. Hautes \u00c9tudes Sci. Publ. Math."},{"key":"9062_CR19","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02684780","volume":"52","author":"P. Deligne","year":"1980","unstructured":"P. Deligne, La conjecture de\u00a0Weil. II, Inst. Hautes \u00c9tudes Sci. Publ. Math. 52, 137\u2013252 (1980). MR 601520 (83c:14017).","journal-title":"Inst. Hautes \u00c9tudes Sci. Publ. Math."},{"issue":"3","key":"9062_CR20","doi-asserted-by":"crossref","first-page":"631","DOI":"10.2307\/2372974","volume":"82","author":"B. Dwork","year":"1960","unstructured":"B. Dwork, On the rationality of the zeta function of an algebraic variety, Am. J. Math. 82(3), 631\u2013648 (1960).","journal-title":"Am. J. Math."},{"issue":"2","key":"9062_CR21","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1093\/qmath\/ham036","volume":"59","author":"M. Edmundo","year":"2008","unstructured":"M. Edmundo, N. Peatfield, o-minimal \u010cech cohomology, Q. J. Math. 59(2), 213\u2013220 (2008). MR 2428077.","journal-title":"Q. J. Math."},{"issue":"1","key":"9062_CR22","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1112\/S0024610703004939","volume":"69","author":"A. Gabrielov","year":"2004","unstructured":"A. Gabrielov, N. Vorobjov, T. Zell, Betti numbers of semialgebraic and sub-Pfaffian sets, J. Lond. Math. Soc. (2) 69(1), 27\u201343 (2004). MR 2025325 (2004k:14105).","journal-title":"J. Lond. Math. Soc. (2)"},{"issue":"1","key":"9062_CR23","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1112\/jlms\/jdp006","volume":"80","author":"A. Gabrielov","year":"2009","unstructured":"A. Gabrielov, N. Vorobjov, Approximation of definable sets by compact families, and upper bounds on homotopy and homology, J. Lond. Math. Soc. (2) 80(1), 35\u201354 (2009). MR 2520376.","journal-title":"J. Lond. Math. Soc. (2)"},{"issue":"4","key":"9062_CR24","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01200148","volume":"4","author":"L. Gournay","year":"1993","unstructured":"L. Gournay, J.J. Risler, Construction of roadmaps of semi-algebraic sets, Appl. Algebra Eng. Commun. Comput. 4(4), 239\u2013252 (1993).","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"issue":"1\u20132","key":"9062_CR25","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Grigoriev","year":"1988","unstructured":"D. Grigoriev, Complexity of deciding Tarski algebra, J. Symb. Comput. 5(1\u20132), 65\u2013108 (1988). MR 90b:03054.","journal-title":"J. Symb. Comput."},{"issue":"2","key":"9062_CR26","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202001","volume":"2","author":"D. Grigoriev","year":"1992","unstructured":"D. Grigoriev, N. Vorobjov, Counting connected components of a semi-algebraic set in subexponential time, Comput. Complex. 2(2), 133\u2013186 (1992).","journal-title":"Comput. Complex."},{"key":"9062_CR27","series-title":"Universitext","volume-title":"Using the Borsuk\u2013Ulam Theorem","author":"J. Matou\u0161ek","year":"2003","unstructured":"J. Matou\u0161ek, Using the Borsuk\u2013Ulam Theorem. Universitext (Springer, Berlin, 2003). Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Bj\u00f6rner and G\u00fcnter M. Ziegler. MR 1988723 (2004i:55001)."},{"issue":"1\u20132","key":"9062_CR28","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0304-3975(98)00190-X","volume":"242","author":"K. Meer","year":"2000","unstructured":"K. Meer, Counting problems over the reals, Theoret. Comput. Sci. 242(1\u20132), 41\u201358 (2000). MR 1769145 (2002g:68041).","journal-title":"Theoret. Comput. Sci."},{"key":"9062_CR29","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"C. Papadimitriou, Computational Complexity (Addison-Wesley, San Diego, 1994)."},{"issue":"2","key":"9062_CR30","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"J. Renegar, On the computational complexity and geometry of the first-order theory of the reals. I-III, J. Symb. Comput. 13(2), 255\u2013352 (1992).","journal-title":"J. Symb. Comput."},{"issue":"1","key":"9062_CR31","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U. Sch\u00f6ning","year":"1989","unstructured":"U. Sch\u00f6ning, Probabilistic complexity classes and lowness, J. Comput. Syst. Sci. 39(1), 84\u2013100 (1989) MR 1013721 (91b:68041a).","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9062_CR32","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1215\/S0012-7094-95-08105-8","volume":"81","author":"M. Shub","year":"1995","unstructured":"M. Shub, S. Smale, On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of \u201c $\\mathrm{NP}\\not=\\mathrm{P}$ ?\u201d, Duke Math. J. 81(1), 47\u201354 (1995). A celebration of John F. Nash, Jr. MR 1381969 (97h:03067).","journal-title":"Duke Math. J."},{"key":"9062_CR33","volume-title":"Algebraic Topology","author":"E.H. Spanier","year":"1966","unstructured":"E.H. Spanier, Algebraic Topology (McGraw-Hill Book, New York, 1966). MR 0210112 (35 #1007)."},{"issue":"1","key":"9062_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer, The polynomial-time hierarchy, Theoret. Comput. Sci. 3(1), 1\u201322 (1977). MR 0438810 (55 #11716).","journal-title":"Theoret. Comput. Sci."},{"key":"9062_CR35","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A. Tarski","year":"1951","unstructured":"A. Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd edn. (University of California Press, Berkeley\/Los Angeles, 1951). MR 13,423a.","edition":"2"},{"issue":"5","key":"9062_CR36","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda, PP is as hard as the polynomial-time hierarchy, SIAM J. Comput. 20(5), 865\u2013877 (1991). MR 1115655 (93a:68047).","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9062_CR37","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"L.G. Valiant, V.V. Vazirani, NP is as easy as detecting unique solutions, Theoret. Comput. Sci. 47(1), 85\u201393 (1986). MR 871466 (88i:68021).","journal-title":"Theoret. Comput. Sci."},{"key":"9062_CR38","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1090\/S0002-9904-1949-09219-4","volume":"55","author":"A. Weil","year":"1949","unstructured":"A. Weil, Number of solutions of equations over finite fields, Bull. Am. Math. Soc. 55, 497\u2013508 (1949).","journal-title":"Bull. Am. Math. Soc."},{"issue":"1\u20132","key":"9062_CR39","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"D.Yu. Grigoriev","year":"1988","unstructured":"D.Yu. Grigoriev, N.N. Vorobjov Jr., Solving systems of polynomial inequalities in subexponential time, J. Symb. Comput. 5(1\u20132), 37\u201364 (1988). MR 949112 (89h:13001).","journal-title":"J. Symb. Comput."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-010-9062-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-010-9062-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-010-9062-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,23]],"date-time":"2021-10-23T03:07:52Z","timestamp":1634958472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-010-9062-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2,19]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9062"],"URL":"https:\/\/doi.org\/10.1007\/s10208-010-9062-4","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2,19]]}}}