{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:27:41Z","timestamp":1773228461501,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,11,19]],"date-time":"2011-11-19T00:00:00Z","timestamp":1321660800000},"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":[[2012,6]]},"DOI":"10.1007\/s10208-011-9105-5","type":"journal-article","created":{"date-parts":[[2011,11,18]],"date-time":"2011-11-18T19:10:27Z","timestamp":1321643427000},"page":"327-362","source":"Crossref","is-referenced-by-count":7,"title":["A Complex Analogue of Toda\u2019s Theorem"],"prefix":"10.1007","volume":"12","author":[{"given":"Saugata","family":"Basu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,19]]},"reference":[{"key":"9105_CR1","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.\u00a010 (Springer, Berlin, 2006). MR 1998147 (2004g:14064).","edition":"2"},{"issue":"4","key":"9105_CR2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s10208-010-9062-4","volume":"10","author":"S. Basu","year":"2010","unstructured":"S. Basu, T. Zell, Polynomial hierarchy, Betti numbers, and a real analogue of Toda\u2019s theorem, Found. Comput. Math. 10(4), 429\u2013454 (2010). MR 2657948.","journal-title":"Found. Comput. Math."},{"issue":"2","key":"9105_CR3","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1090\/S0894-0347-08-00630-9","volume":"22","author":"C. Beltr\u00e1n","year":"2009","unstructured":"C. Beltr\u00e1n, L.M. Pardo, Smale\u2019s 17th problem: average polynomial time to compute affine and projective solutions, J. Am. Math. Soc. 22(2), 363\u2013385 (2009). MR 2476778 (2009m:90147).","journal-title":"J. Am. Math. Soc."},{"issue":"1","key":"9105_CR4","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. 21(1), 1\u201346 (1989). MR 90a:68022.","journal-title":"Bull. Am. Math. Soc."},{"key":"9105_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":"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."},{"key":"9105_CR6","series-title":"Quad. Mat., Dept. Math.","first-page":"73","volume-title":"Complexity of Computations and Proofs","author":"P. B\u00fcrgisser","year":"2004","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, ed. by J. Krajicek, Quad. Mat., Dept. Math., vol. 13 (Seconda Univ. Napoli, Caserta, 2004), pp. 73\u2013151. MR 2131406 (2006c:68053)."},{"issue":"2","key":"9105_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":"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":"3","key":"9105_CR8","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.4007\/annals.2011.174.3.8","volume":"174","author":"P. B\u00fcrgisser","year":"2011","unstructured":"P. B\u00fcrgisser, F. Cucker, On a problem posed by Steve Smale, Ann. Math. 174(3), 1785\u20131836 (2011).","journal-title":"Ann. Math."},{"issue":"4","key":"9105_CR9","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."},{"issue":"1\/2","key":"9105_CR10","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0747-7171(88)80004-X","volume":"5","author":"J.H. Davenport","year":"1988","unstructured":"J.H. Davenport, J. Heintz, Real quantifier elimination is doubly exponential, J. Symb. Comput. 5(1\/2), 29\u201335 (1988).","journal-title":"J. Symb. Comput."},{"key":"9105_CR11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02684373","volume":"43","author":"P. Deligne","year":"1974","unstructured":"P. Deligne, La conjecture de Weil. I, Publ. Math. IH\u00c9S 43, 273\u2013307 (1974). MR 0340258 (49 #5013).","journal-title":"Publ. Math. IH\u00c9S"},{"key":"9105_CR12","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02684780","volume":"52","author":"P. Deligne","year":"1980","unstructured":"P. Deligne, La conjecture de Weil. II, Publ. Math. IH\u00c9S 52, 137\u2013252 (1980). MR 601520 (83c:14017)","journal-title":"Publ. Math. IH\u00c9S"},{"issue":"3","key":"9105_CR13","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":"1","key":"9105_CR14","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. 69(1), 27\u201343 (2004). MR 2025325 (2004k:14105).","journal-title":"J. Lond. Math. Soc."},{"key":"9105_CR15","series-title":"Publ. Math. Univ. Strasbourg","volume-title":"Actualit\u2019es Sci. Ind. No. 1252","author":"R. Godement","year":"1958","unstructured":"R. Godement, Topologie alg\u00e9brique et th\u00e9orie des faisceaux, in Actualit\u2019es Sci. Ind. No. 1252. Publ. Math. Univ. Strasbourg, vol. 13 (Hermann, Paris, 1958). MR 0102797 (21 #1583)."},{"issue":"1","key":"9105_CR16","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1006\/ffta.2000.0303","volume":"7","author":"N.M. Katz","year":"2001","unstructured":"N.M. Katz, Sums of Betti numbers in arbitrary characteristic, Finite Fields Appl. 7(1), 29\u201344 (2001). Dedicated to Professor Chao Ko on the occasion of his 90th birthday. MR 1803934 (2002d:14028).","journal-title":"Finite Fields Appl."},{"issue":"2","key":"9105_CR17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.2307\/1971448","volume":"129","author":"H.B. Lawson Jr.","year":"1989","unstructured":"H.B. Lawson Jr., Algebraic cycles and homotopy theory, Ann. Math. 129(2), 253\u2013291 (1989). MR 986794 (90h:14008).","journal-title":"Ann. Math."},{"key":"9105_CR18","series-title":"Lectures on Topological Methods in Combinatorics and Geometry","volume-title":"Universitext","author":"J. Matou\u0161ek","year":"2003","unstructured":"J. Matou\u0161ek, Using the Borsuk\u2013Ulam theorem, in Universitext. Lectures on Topological Methods in Combinatorics and Geometry (Springer, Berlin, 2003). Written in cooperation with Anders Bj\u00f6rner and G\u00fcnter M. Ziegler. MR 1988723 (2004i:55001)."},{"key":"9105_CR19","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"A User\u2019s Guide to Spectral Sequences","author":"J. McCleary","year":"2001","unstructured":"J. McCleary, A User\u2019s Guide to Spectral Sequences, 2nd edn. Cambridge Studies in Advanced Mathematics (Cambridge University Press, Cambridge, 2001).","edition":"2"},{"issue":"1\u20132","key":"9105_CR20","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, Theor. Comput. Sci. 242(1\u20132), 41\u201358 (2000). MR 1769145 (2002g:68041).","journal-title":"Theor. Comput. Sci."},{"key":"9105_CR21","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"C. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, 1994)."},{"issue":"3","key":"9105_CR22","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/j.jco.2007.03.008","volume":"23","author":"P. Scheiblechner","year":"2007","unstructured":"P. Scheiblechner, On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety, J. Complex. 23(3), 359\u2013379 (2007). MR 2330991 (2009d:14020).","journal-title":"J. Complex."},{"issue":"1","key":"9105_CR23","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":"2","key":"9105_CR24","first-page":"459","volume":"6","author":"M. Shub","year":"1993","unstructured":"M. Shub, S. Smale, Complexity of B\u00e9zout\u2019s theorem. I. Geometric aspects, J. Am. Math. Soc. 6(2), 459\u2013501 (1993). MR 1175980 (93k:65045).","journal-title":"J. Am. Math. Soc."},{"issue":"1","key":"9105_CR25","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). (1996), A celebration of John F. Nash, Jr. MR 1381969 (97h:03067).","journal-title":"Duke Math. J."},{"key":"9105_CR26","volume-title":"Algebraic Topology","author":"E.H. Spanier","year":"1966","unstructured":"E.H. Spanier, Algebraic Topology (McGraw-Hill, New York, 1966). MR 0210112 (35 #1007)."},{"issue":"1","key":"9105_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"L. Stockmeyer, The polynomial-time hierarchy, Theor. Comput. Sci. 3(1), 1\u201322 (1976). (1977). MR 0438810 (55 #11716).","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9105_CR28","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":"9105_CR29","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, Theor. Comput. Sci. 47(1), 85\u201393 (1986). MR 871466 (88i:68021).","journal-title":"Theor. Comput. Sci."},{"key":"9105_CR30","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."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-011-9105-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-011-9105-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-011-9105-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T20:10:20Z","timestamp":1560975020000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-011-9105-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,19]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9105"],"URL":"https:\/\/doi.org\/10.1007\/s10208-011-9105-5","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,19]]}}}