{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:14:37Z","timestamp":1778498077252,"version":"3.51.4"},"reference-count":33,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1992,3,1]],"date-time":"1992-03-01T00:00:00Z","timestamp":699408000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1992,3,1]],"date-time":"1992-03-01T00:00:00Z","timestamp":699408000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2012,6,2]],"date-time":"2012-06-02T00:00:00Z","timestamp":1338595200000},"content-version":"vor","delay-in-days":7398,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Symbolic Computation"],"published-print":{"date-parts":[[1992,3]]},"DOI":"10.1016\/s0747-7171(10)80003-3","type":"journal-article","created":{"date-parts":[[2010,6,4]],"date-time":"2010-06-04T04:35:34Z","timestamp":1275626134000},"page":"255-299","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":344,"title":["On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals"],"prefix":"10.1016","volume":"13","author":[{"given":"James","family":"Renegar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0747-7171(10)80003-3_bib1","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/S0747-7171(88)80016-6","article-title":"A bibliography of quantifier elimination for real closed fields","volume":"5","author":"Arnon","year":"1988","journal-title":"J. Symbolic Computation"},{"key":"10.1016\/S0747-7171(10)80003-3_bib2","first-page":"80","article-title":"Lower bounds for algebraic computation trees","author":"Ben-Or","year":"1983"},{"key":"10.1016\/S0747-7171(10)80003-3_bib3","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0022-0000(86)90029-2","article-title":"The complexity of elementary algebra and geometry","volume":"32","author":"Ben-Or","year":"1986","journal-title":"J. Comp. System Sci."},{"key":"10.1016\/S0747-7171(10)80003-3_bib4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","article-title":"On a theory of computation and complexity over the real numbers: NP-compIeteness, recursive functions and universal machines","volume":"21","author":"L. Shub M.","year":"1989","journal-title":"Bulletin of the American Mathematical Society"},{"key":"10.1016\/S0747-7171(10)80003-3_bib5","article-title":"The Godel incompleteness theorem and decidability over a ring","author":"Blum","year":"1992"},{"key":"10.1016\/S0747-7171(10)80003-3_bib6","first-page":"460","article-title":"Some algebraic and geometric computations in PSPACE","author":"Canny","year":"1988"},{"key":"10.1016\/S0747-7171(10)80003-3_bib7","first-page":"241","article-title":"J. Symbolic Computation","volume":"9","author":"characteristic polynomials","year":"1990","journal-title":"J. Symbolic Computation"},{"key":"10.1016\/S0747-7171(10)80003-3_bib8","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BFb0030287","article-title":"Complexity of quantifier elimination in the theory of algebraically closed fields","volume":"176","author":"Chistov","year":"1984","journal-title":"Lecture Notes in Computer Science"},{"key":"10.1016\/S0747-7171(10)80003-3_bib9","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1002\/cpa.3160220202","article-title":"Decision procedures for real and p-adic fields","volume":"22","author":"Cohen","year":"1969","journal-title":"Communications in Pure and Applied Mathematics"},{"key":"10.1016\/S0747-7171(10)80003-3_bib10","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/3-540-07407-4_17","article-title":"Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Second GI Conference on Automata Theory and Formal Languages","volume":"33","author":"Collins","year":"1975","journal-title":"Lecture Notes in Computer Science"},{"key":"10.1016\/S0747-7171(10)80003-3_bib11","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","article-title":"Fast parallel matrix inversion algorithms","volume":"5","author":"Csanky","year":"1976","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0747-7171(10)80003-3_bib12","article-title":"Algorithmes rapides en sequential et en parallele pour l'\u00e9limination de quantificateurs en g\u00e9om\u00e9trie \u00e9l\u00e9mentaire","author":"Fitchas","year":"1987"},{"key":"10.1016\/S0747-7171(10)80003-3_bib13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-4049(90)90159-F","article-title":"Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields","volume":"67","author":"Fitchas","year":"1990","journal-title":"J. Pure App. Algebra"},{"key":"10.1016\/S0747-7171(10)80003-3_bib14","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1070\/IM1987v029n02ABEH000979","article-title":"The complexity of the decision problem for the first order theory of algebraically closed fields","volume":"29","author":"D. Yu.","year":"1987","journal-title":"Math. USSR Izvestiya"},{"key":"10.1016\/S0747-7171(10)80003-3_bib15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","article-title":"The complexity of deciding Tarski algebra","volume":"5","author":"D. Yu.","year":"1988","journal-title":"J. Symbolic Computation"},{"key":"10.1016\/S0747-7171(10)80003-3_bib16","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","article-title":"Solving systems of polynomial inequalities in subexponential time","volume":"5","author":"D. Yu.","year":"1988","journal-title":"J. Symbolic Computation"},{"key":"10.1016\/S0747-7171(10)80003-3_bib17","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","article-title":"Definability and fast quantifier elimination in algebraically closed fields","volume":"24","author":"Heintz","year":"1983","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0747-7171(10)80003-3_bib18","first-page":"293","article-title":"On the complexity of semialgebraic sets","author":"Heintz","year":"1989"},{"key":"10.1016\/S0747-7171(10)80003-3_bib19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.24033\/bsmf.2138","article-title":"Sur la complexit\u00e9 du principe de Tarski-Seidenberg","volume":"118","author":"Heintz","year":"1990","journal-title":"Bull Soc Math. France"},{"key":"10.1016\/S0747-7171(10)80003-3_bib20","article-title":"Quantifier elimination in the first-order theory of algebraically closed fields","author":"Ierardi","year":"1989"},{"key":"10.1016\/S0747-7171(10)80003-3_bib21","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","article-title":"A new polynomial-time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984","journal-title":"Combinatorica"},{"key":"10.1016\/S0747-7171(10)80003-3_bib22","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachiyan","year":"1979","journal-title":"Soviet Mathematics Doklady"},{"key":"10.1016\/S0747-7171(10)80003-3_bib23","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","article-title":"On the Betti numbers of real varieties","volume":"15","author":"Milnor","year":"1964","journal-title":"Proceedings of the American Mathematical Society"},{"key":"10.1016\/S0747-7171(10)80003-3_bib24","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01580724","article-title":"A polynomial time algorithm, based on Newton's method, for linear programming","volume":"40","author":"Renegar","year":"1988","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0747-7171(10)80003-3_bib25","first-page":"291","article-title":"A faster PSPACE algorithm for the existential theory of the reals","author":"Renegar","year":"1988"},{"key":"10.1016\/S0747-7171(10)80003-3_bib26","doi-asserted-by":"crossref","DOI":"10.1137\/0221060","article-title":"On the computational complexity of approximating solutions for real algebraic formulae","author":"Renegar","year":"1992","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0747-7171(10)80003-3_bib27","article-title":"Recent progress on the complexity of the decision problem for the reals","author":"Renegar","year":"1992","journal-title":"Proceedings of the DJMACS Workshop on Algebraic Methods in Geometric Computations"},{"key":"10.1016\/S0747-7171(10)80003-3_bib28","doi-asserted-by":"crossref","first-page":"365","DOI":"10.2307\/1969640","article-title":"A new decision method for elementary algebra","volume":"60","author":"Seidenberg","year":"1954","journal-title":"Annals of Mathematics"},{"key":"10.1016\/S0747-7171(10)80003-3_bib29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","article-title":"Lower bounds for algebraic decision trees","volume":"3","author":"Steele","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/S0747-7171(10)80003-3_bib30","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","article-title":"A strongly polynomial algorithm for solving combinatorial linear programs","volume":"34","author":"Tardos","year":"1986","journal-title":"Operations Research"},{"key":"10.1016\/S0747-7171(10)80003-3_bib31","series-title":"A Decision Method for Elementary Algebra and Geometry","author":"Tarski","year":"1951"},{"key":"10.1016\/S0747-7171(10)80003-3_bib32","doi-asserted-by":"crossref","first-page":"7","DOI":"10.2307\/2274424","article-title":"Alfred Tarski's elimination theory for real closed fields","volume":"53","author":"Van Den Dries","year":"1988","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0747-7171(10)80003-3_bib33","series-title":"Modern Algebra","author":"Van Der Waerden","year":"1950"}],"container-title":["Journal of Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717110800033?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717110800033?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:11:35Z","timestamp":1760058695000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0747717110800033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,3]]}},"alternative-id":["S0747717110800033"],"URL":"https:\/\/doi.org\/10.1016\/s0747-7171(10)80003-3","relation":{},"ISSN":["0747-7171"],"issn-type":[{"value":"0747-7171","type":"print"}],"subject":[],"published":{"date-parts":[[1992,3]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals","name":"articletitle","label":"Article Title"},{"value":"Journal of Symbolic Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0747-7171(10)80003-3","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1992 Academic Press Limited. Published by Elsevier Ltd. All rights reserved.","name":"copyright","label":"Copyright"}]}}