{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:12:34Z","timestamp":1761610354790,"version":"build-2065373602"},"reference-count":16,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,29]],"date-time":"2013-07-29T00:00:00Z","timestamp":1375056000000},"content-version":"vor","delay-in-days":3954,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Electronic Notes in Theoretical Computer Science"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s1571-0661(04)80537-1","type":"journal-article","created":{"date-parts":[[2004,9,29]],"date-time":"2004-09-29T12:47:47Z","timestamp":1096462067000},"page":"7-14","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["On sparseness and Turing reducibility over the reals"],"prefix":"10.1016","volume":"67","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB1","series-title":"Complexity Theory: current research","first-page":"1","article-title":"Reductions to sets of low information content","author":"Arvind","year":"1993"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","article-title":"On isomorphism and density of NP and other complete sets","volume":"6","author":"Berman","year":"1977","journal-title":"SIAM Journal on Computing"},{"year":"1998","series-title":"Complexity and Real Computation","author":"Blum","key":"10.1016\/S1571-0661(04)80537-1_NEWBIB3"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB4","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-completeness, recursive functions and universal machines","volume":"21","author":"Blum","year":"1989","journal-title":"Bulletin of the Amer. Math. Soc"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB5","unstructured":"M. Coste. An Introduction to o-minimal Geometry. Istituti Editoriali e Poligrafici Internazionali, 2000."},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/S0097539700379346","article-title":"There are no sparse NPW-hard sets","volume":"31","author":"Cucker","year":"2001","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB7","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0020-0190(97)00060-4","article-title":"Complexity and dimension","volume":"62","author":"Cucker","year":"1997","journal-title":"Information Processing Letters"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(94)00069-7","article-title":"Complexity separations in Koiran's weak model","volume":"133","author":"Cucker","year":"1994","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB9","first-page":"80","article-title":"p-adic and real subanalytic sets","volume":"128","author":"Denef","year":"1998","journal-title":"Ann. of Math"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB10","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/S0304-3975(00)00203-6","article-title":"Sparse NP-complete problems over the reals with addition","volume":"255","author":"Fournier","year":"2001","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB11","doi-asserted-by":"crossref","unstructured":"H. Fournier and P. Koiran. Lower bounds are not easier over the reals: Inside PH. In 28th International Colloquium on Automata, Languages and Programming, volume 1853 of Lect. Notes in Comp. Sci., pages 832\u2013843. Springer-Verlag, 2000","DOI":"10.1007\/3-540-45022-X_70"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1006\/jcss.1997.1478","article-title":"A weak version of the Blum, Shub & Smale model","volume":"54","author":"Koiran","year":"1997","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB13","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","article-title":"Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis","volume":"25","author":"Mahaney","year":"1982","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB14","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/0885-064X(92)90007-X","article-title":"A note on a P \u2260 NP result for a restricted class of real machines","volume":"8","author":"Meer","year":"1992","journal-title":"Journal of Complexity"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB15","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1215\/S0012-7094-96-08416-1","article-title":"Geometric categories and o-minimal structures","volume":"84","author":"van den Dries","year":"1996","journal-title":"Duke Math. J"},{"key":"10.1016\/S1571-0661(04)80537-1_NEWBIB16","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s000290050052","article-title":"A theorem of the complement and some new o-minimal structures","volume":"5","author":"Wilkie","year":"1999","journal-title":"Selecta Math. (N.S.)"}],"container-title":["Electronic Notes in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104805371?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104805371?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:05:20Z","timestamp":1761609920000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571066104805371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":16,"alternative-id":["S1571066104805371"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0661(04)80537-1","relation":{},"ISSN":["1571-0661"],"issn-type":[{"type":"print","value":"1571-0661"}],"subject":[],"published":{"date-parts":[[2002,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On sparseness and Turing reducibility over the reals","name":"articletitle","label":"Article Title"},{"value":"Electronic Notes in Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S1571-0661(04)80537-1","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2002 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}