{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:12Z","timestamp":1725488532124},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_3","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"35-52","source":"Crossref","is-referenced-by-count":5,"title":["Circuits versus Trees in Algebraic Complexity"],"prefix":"10.1007","author":[{"given":"Pascal","family":"Koiran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"issue":"6","key":"3_CR2","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S. Basu","year":"1996","unstructured":"S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM, 43(6):1002\u20131045, 1996.","journal-title":"Journal of the ACM"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic settings for the problem \u201cP\u2260NP?\u201d. In J. Renegar, M. Shub, and S. Smale, editors, The Mathematics of Numerical Analysis, volume 32 of Lectures in Applied Mathematics, pages 125\u2013144. American Mathematical Society, 1996.","DOI":"10.1007\/978-1-4612-0701-6_7"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"issue":"1","key":"3_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1\u201346, July 1989.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"3_CR6","unstructured":"M. Bourgade. S\u00e9parations et transferts dans la hi\u00e9rarchie polynomiale des groupes ab\u00e9liens infinis. preprint, 1999."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0168-0072(98)00060-8","volume":"99","author":"O. Chapuis","year":"1999","unstructured":"O. Chapuis and P. Koiran. Saturation and stability in the theory of computation over the reals. Annals of Pure and Applied Logic, 99:1\u201349, 1999.","journal-title":"Annals of Pure and Applied Logic"},{"key":"3_CR9","unstructured":"A. Chistov and D. Grigoriev. Subexponential-time solving systems of algebraic equations I, II. Preprints LOMI E-9-83, E-10-83, Leningrad, 1983."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"A. Chistov and D. Grigoriev. Complexity of quantifier elimination in the theory of algebraically closed fields. In Proc. MFCS\u201984, volume 176 of Lectures Notes in Computer Science, pages 17\u201331. Springer-Verlag, 1984.","DOI":"10.1007\/BFb0030287"},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1137\/S0097539794270340","volume":"26","author":"F. Cucker","year":"1997","unstructured":"F. Cucker and D. Grigoriev. On the power of real Turing machines with binary inputs. SIAM Journal on Computing, 26(1):243\u2013254, 1997.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jcom.1995.1018","volume":"11","author":"F. Cucker","year":"1995","unstructured":"F. Cucker and P. Koiran. Computing over the reals with addition and order: Higher complexity classes. Journal of Complexity, 11:358\u2013376, 1995.","journal-title":"Journal of Complexity"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-4049(90)90159-F","volume":"67","author":"N. Fichtas","year":"1990","unstructured":"N. Fichtas, A. Galligo, and J. Morgenstern. Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields. Journal of Pure and Applied Algebra, 67:1\u201314, 1990.","journal-title":"Journal of Pure and Applied Algebra"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"H. Fournier and P. Koiran. Are lower bounds easier over the reals? In Proc. 30th ACM Symposium on Theory of Computing, pages 507\u2013513, 1998.","DOI":"10.1145\/276698.276864"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"H. Fournier and P. Koiran. Lower bounds are not easier over the reals: Inside PH. LIP Research Report 99-21, Ecole Normale Sup\u00e9rieure de Lyon, 1999.","DOI":"10.1145\/276698.276864"},{"issue":"1","key":"3_CR16","doi-asserted-by":"publisher","first-page":"92","DOI":"10.2307\/2275252","volume":"59","author":"J. B. Goode","year":"1994","unstructured":"J. B. Goode. Accessible telephone directories. Journal of Symbolic Logic, 59(1):92\u2013105, 1994.","journal-title":"Journal of Symbolic Logic"},{"key":"3_CR17","unstructured":"J. E. Goodman and J. O\u2019Rourke, editors. Handbook of Discrete and Computational Geometry. CRC Press, 1997."},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Grigoriev","year":"1988","unstructured":"D. Grigoriev. Complexity of deciding Tarksi algebra. Journal of Symbolic Computation, 5:65\u2013208, 1988.","journal-title":"Journal of Symbolic Computation"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"D. Grigoriev. Complexity of quantifier elimination in the theory of ordinary differential equations. In Proc. Eurocal\u201987, volume 378 of Lectures Notes in Computer Science, pages 11\u201325. Springer-Verlag, 1989.","DOI":"10.1007\/3-540-51517-8_81"},{"key":"3_CR20","unstructured":"D. Grigoriev. Topological complexity of the range searching. To appear in Journal of Complexity."},{"issue":"4","key":"3_CR21","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BF01270388","volume":"6","author":"D. Grigoriev","year":"1996","unstructured":"D. Grigoriev, M. Karpinski, and R. Smolensky. Randomization and the computational power of algebraic and analytic decision trees. Computational Complexity, 6(4):376\u2013388, 1996\/97.","journal-title":"Computational Complexity"},{"issue":"2","key":"3_CR22","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1137\/S0097539793245015","volume":"24","author":"D. Grigoriev","year":"1995","unstructured":"D. Grigoriev, M. Singer, and A. Yao. On computing algebraic functions using logarithms and exponentials. SIAM Journal on Computing, 24(2):242\u2013246, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0304-3975(95)00159-X","volume":"2","author":"D. Grigoriev","year":"1996","unstructured":"D. Grigoriev and N. Vorobjov. Complexity lower bounds for computation trees with elementary transcendental function gates. Theoretical Computer Science, 2:185\u2013214, 1996.","journal-title":"Theoretical Computer Science"},{"key":"3_CR24","unstructured":"W. Hodges. Model Theory. Encyclopedia of Mathematics and its Applications 42. Cambridge University Press, 1993."},{"issue":"1","key":"3_CR25","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(93)00063-B","volume":"133","author":"P. Koiran","year":"1994","unstructured":"P. Koiran. Computing over the reals with addition and order. Theoretical Computer Science, 133(1):35\u201348, 1994.","journal-title":"Theoretical Computer Science"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"P. Koiran. VC dimension in circuit complexity. In Proc. 11th IEEE Conference on Computational Complexity, pages 81\u201385, 1996.","DOI":"10.1109\/CCC.1996.507671"},{"issue":"1","key":"3_CR27","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jcom.1997.0433","volume":"13","author":"P. Koiran","year":"1997","unstructured":"P. Koiran. Elimination of constants from machines over algebraically closed fields. Journal of Complexity, 13(1):65\u201382, 1997. Erratum on http:\/\/www.enslyon.fr\/~koiran .","journal-title":"Journal of Complexity"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jcss.1997.1478","volume":"54","author":"P. Koiran","year":"1997","unstructured":"P. Koiran. A weak version of the Blum, Shub & Smale model. Journal of Computer and System Sciences, 54:177\u2013189, 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0885-064X(92)90007-X","volume":"8","author":"K. Meer","year":"1992","unstructured":"K. Meer. A note on a P \u2260 N P result for a restricted class of real machines. Journal of Complexity, 8:451\u2013453, 1992.","journal-title":"Journal of Complexity"},{"issue":"2","key":"3_CR30","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1006\/inco.1993.1057","volume":"106","author":"S. Meiser","year":"1993","unstructured":"S. Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106(2):286\u2013303, 1993.","journal-title":"Information and Computation"},{"issue":"3","key":"3_CR31","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"F. Meyer auf der Heide. A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM, 31(3):668\u2013676, 1984.","journal-title":"Journal of the ACM"},{"issue":"3","key":"3_CR32","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1145\/44483.44490","volume":"35","author":"F. Meyer auf der Heide","year":"1988","unstructured":"F. Meyer auf der Heide. Fast algorithms for n-dimensional restrictions of hard problems. Journal of the ACM, 35(3):740\u2013747, 1988.","journal-title":"Journal of the ACM"},{"key":"3_CR33","first-page":"435","volume":"I","author":"C. Michaux","year":"1989","unstructured":"C Michaux. Une remarque \u00e0 propos des machines sur \u211d introduites par Blum, Shub et Smale. C. R. Acad. Sci. Paris, 309, S\u00e9rie I:435\u2013437, 1989.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"3_CR34","unstructured":"B. Poizat. Cours de Th\u00e9orie des Mod\u00e8les. Nur Al-Mantiq Wal-Ma\u2019rifah 1. 1985."},{"key":"3_CR35","unstructured":"B. Poizat. Les Petits Cailloux. Nur Al-Mantiq Wal-Ma\u2019rifah 3. Al\u00e9as, Lyon, 1995."},{"issue":"2","key":"3_CR36","doi-asserted-by":"publisher","first-page":"803","DOI":"10.2307\/2586502","volume":"64","author":"N. Portier","year":"1999","unstructured":"N. Portier. Stabilit\u00e9 polynomiale des corps diff\u00e9rentiels. Journal of Symbolic Logic, 64(2):803\u2013816, 1999.","journal-title":"Journal of Symbolic Logic"},{"issue":"3","key":"3_CR37","doi-asserted-by":"publisher","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. parts I, II, III. Journal of Symbolic Computation, 13(3):255\u2013352, March 1992.","journal-title":"Journal of Symbolic Computation"},{"issue":"1","key":"3_CR38","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1215\/S0012-7094-95-08105-8","volume":"81","author":"M. Shub","year":"1996","unstructured":"M. Shub and S. Smale. On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of \u201cP=NP\u201d. Duke Mathematical Journal, 81(1):47\u201354, 1996.","journal-title":"Duke Mathematical Journal"},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0885-064X(87)90021-5","volume":"3","author":"S. Smale","year":"1987","unstructured":"S. Smale. On the topology of algorithms. I. Journal of Complexity, 3:81\u201389, 1987.","journal-title":"Journal of Complexity"},{"key":"3_CR40","unstructured":"S. Smale. On the P=NP problem over the complex numbers. Lecture given at the MSRI workshop on Complexity of Continuous and Algebraic Mathematics, November 1998. Lecture on video at http:\/\/www.msri.org ."},{"key":"3_CR41","unstructured":"V. A. Vassiliev. Complements of Discriminants of Smooth Maps: Topology and Applications. Translations of Mathematical Monographs 98. American Mathematical Society, 1994."},{"key":"3_CR42","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BFb0016236","volume-title":"Mathematical Foundations of Computer Science","author":"J. Gathen von zur","year":"1986","unstructured":"J. von zur Gathen. Parallel arithmetic computations: a survey. In Mathematical Foundations of Computer Science, volume 233 of Lecture Notes in Computer Science, pages 93\u2013112. Springer-Verlag, 1986."}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:10:25Z","timestamp":1556734225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}