{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:27:40Z","timestamp":1773228460787,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540677154","type":"print"},{"value":"9783540450221","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_70","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T18:57:25Z","timestamp":1194980245000},"page":"832-843","source":"Crossref","is-referenced-by-count":13,"title":["Lower Bounds Are Not Easier over the Reals: Inside PH"],"prefix":"10.1007","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Koiran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"70_CR1","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"},{"key":"70_CR2","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":"70_CR3","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":"70_CR4","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":"70_CR5","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":"70_CR6","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\u2260NP result for a restricted class of real machines. Journal of Complexity, 8:451\u2013453, 1992.","journal-title":"Journal of Complexity"},{"issue":"3","key":"70_CR7","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer Heide auf der","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":"70_CR8","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1145\/44483.44490","volume":"35","author":"F. Meyer Heide auf der","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":"70_CR9","volume-title":"Nur Al-Mantiq Wal-Ma\u2019rifah","author":"B. Poizat","year":"1995","unstructured":"B. Poizat. Les Petits Cailloux. Nur Al-Mantiq Wal-Ma\u2019rifah 3. Al\u00e9as, Lyon, 1995."},{"key":"70_CR10","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver. Theory of Linear and Integer Programming. Wiley, New-York, 1986."},{"issue":"1","key":"70_CR11","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":"70_CR12","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":"70_CR13","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Completeness classes in algebra. In Proc. 11th ACM Symposium on Theory of Computing, pages 249\u2013261, 1979.","DOI":"10.1145\/800135.804419"},{"key":"70_CR14","unstructured":"L. G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic (an International Symposium held in honour of Ernst Specker), pages 365\u2013380. Monographie n o 30 de L\u2019Enseignement Math\u00e9matique, 1982."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_70","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T07:25:32Z","timestamp":1556954732000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_70","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}