{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:57Z","timestamp":1725490257010},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_2","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"3-17","source":"Crossref","is-referenced-by-count":4,"title":["On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity"],"prefix":"10.1007","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jcom.1999.0526","volume":"16","author":"M. Aldaz","year":"2000","unstructured":"M. Aldaz, J. Heintz, G. Matera, J. L. Monta\u00f1a, and L. M. Pardo. Time-space tradeoffs in algebraic complexity theory. J. Compl., 16:2\u201349, 2000.","journal-title":"J. Compl."},{"key":"2_CR2","unstructured":"A. Alder. Grenzrang und Grenzkomplexit\u00e4t aus algebraischer und topologischer Sicht. PhD thesis, Z\u00fcrich University, 1984."},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X","volume":"14","author":"A. I. Barvinok","year":"1999","unstructured":"A. I. Barvinok. Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Random Structures and Algorithms, 14:29\u201361, 1999.","journal-title":"Random Structures and Algorithms"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcom.1997.0435","volume":"13","author":"W. Baur","year":"1997","unstructured":"W. Baur. Simplified lower bounds for polynomials with algebraic coefficients. J. Compl., 13:38\u201341, 1997.","journal-title":"J. Compl."},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s000370050001","volume":"8","author":"W. Baur","year":"1999","unstructured":"W. Baur and K. Halupczok. On lower bounds for the complexity of polynomials and their multiples. Comp. Compl., 8:309\u2013315, 1999.","journal-title":"Comp. Compl."},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"S. Berkowitz","year":"1983","unstructured":"S. Berkowitz, C. Rackoff, S. Skyum, and L. Valiant. Fast parallel computation of polynomials using few processors. SIAM J. Comp., 12:641\u2013644, 1983.","journal-title":"SIAM J. Comp."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic Settings for the Problem \u201cP \u2260 NP?\u201d. In The mathematics of numerical analysis, number 32 in Lectures in Applied Mathematics, pages 125\u2013144. Amer. Math. Soc., 1996.","DOI":"10.1007\/978-1-4612-0701-6_7"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"2_CR9","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. Bull. Amer. Math. Soc., 21:1\u201346, 1989.","journal-title":"Bull. Amer. Math. Soc."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser. The complexity of factors of multivariate polynomials. Preprint, University of Paderborn, 2001, submitted.","DOI":"10.1109\/SFCS.2001.959912"},{"key":"2_CR11","first-page":"73","volume":"3","author":"P. B\u00fcrgisser","year":"1999","unstructured":"P. B\u00fcrgisser. On the structure of Valiant\u2019s complexity classes. Discr. Math. Theoret. Comp. Sci., 3:73\u201394, 1999.","journal-title":"Discr. Math. Theoret. Comp. Sci."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and Computation in Mathematics. Springer Verlag, 2000.","DOI":"10.1007\/978-3-662-04179-6"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0304-3975(99)00183-8","volume":"235","author":"P. B\u00fcrgisser","year":"2000","unstructured":"P. B\u00fcrgisser. Cook\u2019s versus Valiant\u2019s hypothesis. Theoret. Comp. Sci., 235:71\u201388, 2000.","journal-title":"Theoret. Comp. Sci."},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer Verlag, 1997.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1006\/jcom.1993.1016","volume":"9","author":"P. B\u00fcrgisser","year":"1993","unstructured":"P. B\u00fcrgisser, M. Karpinski, and T. Lickteig. On randomized semialgebraic decision complexity. J. Compl., 9:231\u2013251, 1993.","journal-title":"J. Compl."},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0885-064X(92)90022-4","volume":"8","author":"P. B\u00fcrgisser","year":"1992","unstructured":"P. B\u00fcrgisser, T. Lickteig, and M. Shub. Test complexity of generic polynomials. J. Compl., 8:203\u2013215, 1992.","journal-title":"J. Compl."},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comp., 9:251\u2013280, 1990.","journal-title":"J. Symb. Comp."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther. On real Turing machines that toss coins. In Proc. 27th ACM STOC, Las Vegas, pages 335\u2013342, 1995.","DOI":"10.1145\/225058.225155"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"H. Fournier and P. Koiran. Are lower bounds easier over the reals? In Proc. 30th ACM STOC, pages 507\u2013513, 1998.","DOI":"10.1145\/276698.276864"},{"key":"2_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1007\/3-540-45022-X_70","volume-title":"Proc. ICALP 2000","author":"H. Fournier","year":"2000","unstructured":"H. Fournier and P. Koiran. Lower bounds are not easier over the reals: Inside PH. In Proc. ICALP 2000, LNCS 1853, pages 832\u2013843, 2000."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0747-7171(87)80063-9","volume":"4","author":"J. Gathen von zur","year":"1987","unstructured":"J. von zur Gathen. Feasible arithmetic computations: Valiant\u2019s hypothesis. J. Symb. Comp., 4:137\u2013172, 1987.","journal-title":"J. Symb. Comp."},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(86)90038-1","volume":"46","author":"B. Griesser","year":"1986","unstructured":"B. Griesser. Lower bounds for the approximative complexity. Theoret. Comp. Sci., 46:329\u2013338, 1986.","journal-title":"Theoret. Comp. Sci."},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"D.Yu. Grigoriev and M. Karpinski. Randomized quadratic lower bound for knapsack. In Proc. 29th ACM STOC, pages 76\u201385, 1997.","DOI":"10.1145\/258533.258555"},{"issue":"2","key":"2_CR24","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"J. Grollmann and A. L. Selman. Complexity measures for public-key cryptosystems. SIAM J. Comp., 17(2):309\u2013335, 1988.","journal-title":"SIAM J. Comp."},{"key":"2_CR25","doi-asserted-by":"publisher","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. Journal of Complexity, 9:471\u2013498, 1993.","journal-title":"Journal of Complexity"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"M. R. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Electronic Colloquium on Computational Complexity, 2000. Report No. 79.","DOI":"10.1145\/380752.380877"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"E. Kaltofen. Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. In Proc. 19th ACM STOC, pages 443\u2013452, 1986.","DOI":"10.1145\/28395.28443"},{"key":"2_CR28","first-page":"375","volume-title":"Randomness and Computation","author":"E. Kaltofen","year":"1989","unstructured":"E. Kaltofen. Factorization of polynomials given by straight-line programs. In S. Micali, editor, Randomness and Computation, pages 375\u2013412. JAI Press, Greenwich CT, 1989."},{"key":"2_CR29","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. Theoret. Comp. Sci., 133:35\u201347, 1994.","journal-title":"Theoret. Comp. Sci."},{"key":"2_CR30","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. J. Comp. Syst. Sci., 54:177\u2013189, 1997.","journal-title":"J. Comp. Syst. Sci."},{"key":"2_CR31","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/3-540-46541-3_3","volume-title":"Proc. STACS 2000","author":"P. Koiran","year":"2000","unstructured":"P. Koiran. Circuits versus trees in algebraic complexity. In Proc. STACS 2000, number 1770 in LNCS, pages 35\u201352. Springer Verlag, 2000."},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"S. Lang. Fundamentals of Diophantine Geometry. Springer Verlag, 1983.","DOI":"10.1007\/978-1-4757-1810-2"},{"key":"2_CR33","series-title":"Habilitationsschrift","volume-title":"Technical Report TR-90-052","author":"T. Lickteig","year":"1990","unstructured":"T. Lickteig. On semialgebraic decision complexity. Technical Report TR-90-052, Int. Comp. Sc. Inst., Berkeley, 1990. Habilitationsschrift, Universit\u00e4t T\u00fcbingen."},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"N. Linial, A. Samorodnitsky, and A. Wigderson. A deterministic polynomial algorithm for matrix scaling and approximate permanents. In Proc. 30th ACM STOC, pages 644\u2013652, 1998.","DOI":"10.1145\/276698.276880"},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/0022-0000(78)90041-7","volume":"16","author":"R. J. Lipton","year":"1978","unstructured":"R. J. Lipton and L. J. Stockmeyer. Evaluation of polynomials with super-preconditioning. J. Comp. Syst. Sci., 16:124\u2013139, 1978.","journal-title":"J. Comp. Syst. Sci."},{"key":"2_CR36","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:286\u2013303, 1993.","journal-title":"Information and Computation"},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. M. Heide auf der","year":"1984","unstructured":"F. Meyer auf der Heide. A polynomial linear search algorithm for the n-dimensional knapsack problem. J. ACM, 31:668\u2013676, 1984.","journal-title":"J. ACM"},{"key":"2_CR38","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(85)90079-9","volume":"41","author":"F. M. Heide auf der","year":"1985","unstructured":"F. Meyer auf der Heide. Simulating probabilistic by deterministic algebraic computation trees. Theoret. Comp. Sci., 41:325\u2013330, 1985.","journal-title":"Theoret. Comp. Sci."},{"key":"2_CR39","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1145\/44483.44490","volume":"35","author":"F. M. Heide auf der","year":"1988","unstructured":"F. Meyer auf der Heide. Fast algorithms for n-dimensional restrictions of hard problems. J. ACM, 35:740\u2013747, 1988.","journal-title":"J. ACM"},{"key":"2_CR40","unstructured":"B. Poizat. Les Petits Cailloux. Number 3 in Nur Al-Mantiq War-Ma\u2019rifah. Al\u00e9as, Lyon, 1995."},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01374525","volume":"25","author":"A. L. Selman","year":"1992","unstructured":"A. L. Selman. A survey of one-way functions in complexity theory. Math. Systems Theory, 25:203\u2013221, 1992.","journal-title":"Math. Systems Theory"},{"key":"2_CR42","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1215\/S0012-7094-95-08105-8","volume":"81","author":"M. Shub","year":"1995","unstructured":"M. Shub and S. Smale. On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of \u201cNP \u2260 P?\u201d. Duke Math. J., 81:47\u201354, 1995.","journal-title":"Duke Math. J."},{"key":"2_CR43","first-page":"184","volume":"264","author":"V. Strassen","year":"1973","unstructured":"V. Strassen. Vermeidung von Divisionen. Crelles J. Reine Angew. Math., 264:184\u2013202, 1973.","journal-title":"Crelles J. Reine Angew. Math."},{"key":"2_CR44","first-page":"1","volume":"78","author":"V. Strassen","year":"1976","unstructured":"V. Strassen. Einige Resultate \u00fcber Berechnungskomplexit\u00e4t. Jahr. Deutsch. Math. Ver., 78:1\u20138, 1976.","journal-title":"Jahr. Deutsch. Math. Ver."},{"key":"2_CR45","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Completeness classes in algebra. In Proc. 11th ACM STOC, pages 249\u2013261, 1979.","DOI":"10.1145\/800135.804419"},{"key":"2_CR46","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoret. Comp. Sci., 8:189\u2013201, 1979.","journal-title":"Theoret. Comp. Sci."},{"key":"2_CR47","first-page":"365","volume":"30","author":"L. G. Valiant","year":"1982","unstructured":"L. G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic: an International Symposium held in honor of Ernst Specker, volume 30, pages 365\u2013380. Monogr. No. 30 de l\u2019Enseign. Math., 1982.","journal-title":"Logic and Algorithmic: an International Symposium held in honor of Ernst Specker"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:27:40Z","timestamp":1556818060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}