{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T03:12:27Z","timestamp":1783653147947,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540601142","type":"print"},{"value":"9783540494409","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60114-7_16","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:42:09Z","timestamp":1330278129000},"page":"205-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["When polynomial equation systems can be \u201csolved\u201d fast?"],"prefix":"10.1007","author":[{"given":"M.","family":"Giusti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Heintz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. E.","family":"Morais","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L. M.","family":"Pardo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"16_CR1","unstructured":"M.E. Alonso, E. Becker, M.-F. Roy, T. W\u00f6rmann: Zeroes, multiplicities and idempotents for zerodimensional systems, to appear in Proc. MEGA'94, Birkh\u00e4user Progress in Mathematics."},{"key":"16_CR2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF02398884","volume":"166","author":"C. Berenstein","year":"1991","unstructured":"C. Berenstein and A. Yger: Effective B\u00e9zout identities in Q[X 1,...,X n], Acta Math., 166 (1991) 69\u2013120","journal-title":"Acta Math."},{"key":"16_CR3","first-page":"363","volume":"24","author":"C. Berenstein","year":"1991","unstructured":"C. Berenstein and A. Yger: Une Formule de Jacobi et ses cons\u00e9quences, Ann Sci. E.N.S., 4ieme s\u00e9rie, 24 (1991) 363\u2013377","journal-title":"Ann Sci. E.N.S., 4ieme s\u00e9rie"},{"key":"16_CR4","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","volume":"18","author":"S.J. Berkowitz","year":"1984","unstructured":"S.J. Berkowitz: On computing the determinant in small parallel time using a small number of processors, Inf. Proc. Letters 18 (1984) 147\u2013150.","journal-title":"Inf. Proc. Letters"},{"key":"16_CR5","unstructured":"J. Brian\u00e7on: Sur le degr\u00e9 des relations entre polyn\u00f4mes, Comptes Rendues de l'Acad. des Sci. Paris, t., S\u00e9rie I Math (1982) 553\u2013556."},{"key":"16_CR6","doi-asserted-by":"crossref","first-page":"577","DOI":"10.2307\/1971361","volume":"126","author":"D. W. Brownawell","year":"1987","unstructured":"D. W. Brownawell: Bounds for the degree in the Nullstellensatz, Annals of Math. 126 (1987) 577\u2013591.","journal-title":"Annals of Math."},{"key":"16_CR7","unstructured":"L.Caniglia, A.Galligo and J.Heintz: Some new effectivity bounds in computational geometry, In Proc. AAECC-6, T. Mora (Ed.), Springer LN in Comp. Sci. 357(1989) 131\u2013152."},{"key":"16_CR8","first-page":"255","volume":"307","author":"L. Caniglia","year":"1988","unstructured":"L. Caniglia, A. Galligo and J. Heintz: Borne simplement exponentielle pour les degr\u00e9s dans le th\u00e9or\u00e8me des z\u00e9ros sur un corps de caract\u00e9ristique quelconque, C.R. Acad. Sci. Paris, S\u00e9rie I, Math. 307 (1988) 255\u2013258.","journal-title":"C.R. Acad. Sci. Paris, S\u00e9rie I, Math."},{"key":"16_CR9","unstructured":"J. Canny: Some algebraic and geometric problems in PSPACE, Proc. 20-th Ann. ACM Symp. Theory of Computing (1988) 460\u2013467."},{"key":"16_CR10","unstructured":"A.L. Chistov: Polynomial-time computation of the dimension of components of algebraic varieties in zero-characteristic, Preprint Universit\u00e9 Paris Val de Marne."},{"key":"16_CR11","unstructured":"A.L. Chistov, D.Yu. Grigor'ev: Subexponential time solving systems of algebraic equations, LOMI Preprints E-9-83, E-10-83, Leningrad (1983)."},{"key":"16_CR12","unstructured":"F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, K. Werther: On real Turing machines that toss coins."},{"issue":"No.4","key":"16_CR13","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"R.A. Millo De","year":"1978","unstructured":"R.A. De Millo, R.J. Lipton: A probabilistic remark on algebraic program testing, Inf. Proc. Letters, vol. 7, No. 4 (1978) 193\u2013195.","journal-title":"Inf. Proc. Letters"},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0166-218X(91)90109-A","volume":"33","author":"A. Dickenstein","year":"1991","unstructured":"A. Dickenstein, N. Fitchas, M. Giusti, C. Sessa: The membership problem of unmixed ideals is solvable in single exponential time, Discrete Applied Mathematics 33 (1991) 73\u201394.","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR15","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1006\/jsco.1993.1020","volume":"15","author":"T.W. Dub\u00e9","year":"1993","unstructured":"T.W. Dub\u00e9: A combinatorial proof of Effective Nullstellensatz, J. Symb. Comp. 15 (1993) 277\u2013296.","journal-title":"J. Symb. Comp."},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"D. Duval: \u00c9valuation Dynamique et cl\u00f4ture alg\u00e9brique en Axiom, Journal of Pure and Applied Algebra (1994).","DOI":"10.1016\/0022-4049(94)00053-L"},{"key":"16_CR17","volume-title":"Sur la complexit\u00e9 du th\u00e9or\u00e8me des z\u00e9ros","author":"N. Fitchas","year":"1995","unstructured":"N. Fitchas, M. Giusti and F. Smietanski: Sur la complexit\u00e9 du th\u00e9or\u00e8me des z\u00e9ros, to appear in Proceedings of the Second International Conference on Approximation and Optimization, La Habana, 1993, J. Gudatt, ed., Peter Lang Verlag, Frankfurt (1995)."},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"W. Fulton: Intersection theory, Ergebnisse der Mathematik, 3 Folge Band 2, Springer Verlag (1984).","DOI":"10.1007\/978-3-662-02421-8"},{"key":"16_CR19","volume-title":"Pathways to solutions, fixed points and equilibria","author":"C.B. Garc\u00eda","year":"1981","unstructured":"C.B. Garc\u00eda and W. I. Zangwill: Pathways to solutions, fixed points and equilibria, Prentice-Hall, N.J. (1981)"},{"key":"16_CR20","first-page":"93","volume":"233","author":"J. Gathen von zur","year":"1986","unstructured":"J.von zur Gathen: Parallel arithmetic computations: a survey, Proc. 13-th Conf. MFCS. Springer LN Comp. Sci. 233(1986) 93\u2013112.","journal-title":"Proc. 13-th Conf. MFCS. Springer LN Comp. Sci."},{"key":"16_CR21","unstructured":"M.Giusti and J.Heintz: La d\u00e9termination des points isol\u00e9s et de la dimension d'une vari\u00e9t\u00e9 alg\u00e9brique peut se faire en temps polynomial, In Computational Algebraic Geometry and Commutative Algebra, Proceedings of the Cortona Conference on Computational Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano, eds., Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993)."},{"key":"16_CR22","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/BF01200407","volume":"3","author":"M. Giusti","year":"1993","unstructured":"M. Giusti, J. Heintz and J. Sabia: On the efficiency of effective Nullstellens\u00e4tze, Computational Complexity 3 (1993) 56\u201395.","journal-title":"Computational Complexity"},{"key":"16_CR23","unstructured":"L. Gonz\u00e1lez Vega, G. Trujillo: Using symmetric functions to describe the solution of a zero-dimensional ideal, in this volume."},{"key":"16_CR24","unstructured":"K. Haegele, J.L. Monta\u00f1a: Polynomial random test for the equivalence problem of integers given by arithmetic circuits. Stasiakte Humboldt-Universit\u00e4t. Preprint Series X901-B"},{"key":"16_CR25","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","volume":"24","author":"J. Heintz","year":"1983","unstructured":"J. Heintz: Fast quantifier elimination over algebraically closed fields, Theoret. Comp. Sci. 24 (1983) 239\u2013277.","journal-title":"Theoret. Comp. Sci."},{"key":"16_CR26","unstructured":"J. Heintz: On the computational complexity of polynomials and bilinear mappings, in Proc. 5th International Conference Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-5, Menorca 1987, L. Huguet and A. Poli, eds., Springer LN Comput. Sci. 356 (1989) 269\u2013300."},{"key":"16_CR27","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1006\/jcom.1993.1031","volume":"9","author":"J. Heintz","year":"1993","unstructured":"J. Heintz and J. Morgenstern: On the intrinsic complexity of elimination theory, J. of Complexity 9 (1993) 471\u2013498","journal-title":"J. of Complexity"},{"key":"#cr-split#-16_CR28.1","unstructured":"J. Heintz and C.P. Schnorr: Testing Polynomials which are easy to compute, Proc. 12th Ann. ACM Symp. on Computing (1980) 262-268"},{"key":"#cr-split#-16_CR28.2","unstructured":"also in Logic and Algorithmic. An International Symposium held in Honour of Ernst Specker, Monographie No. 30 de l'Enseignement de Math\u00e9matiques, Gen\u00e8ve (1982) 237-254."},{"key":"16_CR29","first-page":"16","volume":"115","author":"J. Heintz","year":"1981","unstructured":"J. Heintz and M. Sieveking: Absolute primality of polynomials is decidable in random polynomial time in the number of the variables, 8th International Colloquium on Automata, Languages and Programming ICALP 81, Springer LN Comput. Sci. 115 (1981) 16\u201328.","journal-title":"Springer LN Comput. Sci."},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"O. Ibarra, H. Moran: Probabilistic algorithms for deciding equivalence of straight-line programs, J. ACM 30, Vol. 1, 217\u2013228","DOI":"10.1145\/322358.322373"},{"issue":"No.1","key":"16_CR31","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1145\/42267.45069","volume":"35","author":"E. Kaltofen","year":"1988","unstructured":"E. Kaltofen: Greatest common divisors of polynomials given by straight line programs, J. ACM 35, No. 1 (1988) 234\u2013264.","journal-title":"J. ACM"},{"key":"16_CR32","first-page":"375","volume-title":"Randomness in Computation, Advances in Computing Research 5","author":"E. Kaltofen","year":"1989","unstructured":"E. Kaltofen: Factorization of polynomials given by straight-line programs, Randomness in Computation, Advances in Computing Research 5, S. Micali, ed., JAI Press Inc., Greenwich, CT. (1989) 375\u2013412."},{"key":"16_CR33","first-page":"963","volume":"1","author":"J. Koll\u00e1r","year":"1988","unstructured":"J. Koll\u00e1r: Sharp Effective Nullstllensatz, J. of A.M.S. 1 (1988) 963\u2013975.","journal-title":"J. of A.M.S."},{"key":"16_CR34","unstructured":"T.Krick and L.M.Pardo: A Computational Method for Diophantine Approximation, To appear in Proc. MEGA '94, Birkh\u00e4user Progress in Mathematics."},{"issue":"no.5","key":"16_CR35","first-page":"407","volume":"318","author":"T. Krick","year":"1994","unstructured":"T. Krick, L.M. Pardo: Une approche informatique pour l'approximation diophantienne, Comptes Rendues de l'Acad. des Sci. Paris, t. 318, S\u00e9rie I, no. 5, (1994) 407\u2013412.","journal-title":"Comptes Rendues de l'Acad. des Sci. Paris"},{"key":"16_CR36","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-1-4612-0441-1_14","volume-title":"Effective methods in algebraic geometry (Castiglioncello, 1990), Prog. Math., vol. 94","author":"Y.N. Lakshman","year":"1991","unstructured":"Y.N. Lakshman, D. Lazard: On the complexity of zero-dimensional algebraic systems, Effective methods in algebraic geometry (Castiglioncello, 1990), Prog. Math., vol. 94, Birkh\u00e4user Boston (1991) 217\u2013225."},{"key":"16_CR37","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-3975(81)90064-5","volume":"15","author":"D. Lazard","year":"1981","unstructured":"D. Lazard: R\u00e9solution des syst\u00e8mes d'\u00e9quations alg\u00e9briques, Theor. Comp. Sci. 15 (1981) 77\u2013110.","journal-title":"Theor. Comp. Sci."},{"key":"16_CR38","doi-asserted-by":"crossref","unstructured":"F.S. Macaulay: The Algebraic Theory of Modular Systems, Cambridge University Press (1916)","DOI":"10.3792\/chmm\/1263317740"},{"key":"16_CR39","doi-asserted-by":"crossref","unstructured":"M. Moeller: Systems of algebraic equations solved by means of endomorphisms, in Proc. 10th International Conference Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-10, Puerto Rico 1993, G. Cohen, T. Mora and O. Moreno, eds., Springer LN Comput. Sci.","DOI":"10.1007\/3-540-56686-4_32"},{"key":"16_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01270397","volume":"4","author":"J.L. Monta\u00f1a","year":"1993","unstructured":"J.L. Monta\u00f1a and L.M. Pardo: Lower Bounds for Arithmetic Networks, AAECC, vol. 4 (1993), 1\u201324.","journal-title":"AAECC"},{"key":"16_CR41","unstructured":"L.M. Pardo: How lower and upper complexity bounds meet in elimination theory, in this volume."},{"key":"16_CR42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4064\/aa-58-1-1-25","volume":"58","author":"P. Philippon","year":"1991","unstructured":"P. Philippon: D\u00e9nominateurs dans le th\u00e9or\u00e8me des z\u00e9ros de Hilbert, Acta. Arith. 58 (1991) 1\u201325.","journal-title":"Acta. Arith."},{"key":"16_CR43","unstructured":"J. Sabia and P. Solern\u00f3: Bounds for traces in complete intersections and degrees in the Nullstellensatz, To appear in AAECC Journal (1993)."},{"key":"16_CR44","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"J.T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities, J. ACM 27 (1980) 701\u2013717","journal-title":"J. ACM"},{"key":"16_CR45","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(94)90122-8","volume":"133","author":"M. Shub","year":"1994","unstructured":"M. Shub, S. Smale: Complexity of B\u00e9zout's theorem V: Polynomial time, Theoretical Comp. Sci. 133 (1994) 141\u2013164.","journal-title":"Theoretical Comp. Sci."},{"key":"16_CR46","doi-asserted-by":"crossref","unstructured":"M. Shub, S. Smale: On the intractability of Hilbert's Nullstellensatz and an algebraic version of NP \u2260 P?, IBM Research Report, Yorktown Heights (1994)","DOI":"10.1215\/S0012-7094-95-08105-8"},{"key":"16_CR47","unstructured":"V. Strassen: Algebraic Complexity Theory, Handbook of Theoretical Computer Science, ch. 11 (1990) 634\u2013671."},{"key":"16_CR48","first-page":"184","volume":"264","author":"V. Strassen","year":"1973","unstructured":"V. Strassen: Vermeidung von Divisionen, Crelle J. Reine Angew. Math. 264 (1973) 184\u2013202.","journal-title":"Crelle J. Reine Angew. Math."},{"key":"16_CR49","first-page":"216","volume":"72","author":"R.E. Zippel","year":"1979","unstructured":"R.E. Zippel: Probabilistic Algorithms for Sparse Polynomials, LNCS, Vol 72 (1979) 216\u2013226","journal-title":"LNCS"}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60114-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T09:24:32Z","timestamp":1640942672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60114-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601142","9783540494409"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/3-540-60114-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}