{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:55Z","timestamp":1725490255708},"publisher-location":"Berlin, Heidelberg","reference-count":12,"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_25","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"285-291","source":"Crossref","is-referenced-by-count":0,"title":["There Are No Sparse NPw-Hard Sets"],"prefix":"10.1007","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dima","family":"Grigoriev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"V. Arvind, Y. Han, L. Hemachandra, J. K\u00f6bler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Sch\u00f6ning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. In K. Ambos-Spies, S. Homer, and U. Sch\u00f6ning, editors, Complexity Theory: current research, pages 1\u201345. Cambridge University Press, 1993.","key":"25_CR1","DOI":"10.1007\/3-540-55719-9_72"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets. SIAM Journal on Computing, 6:305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.","key":"25_CR3","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"25_CR4","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 Amer. Math. Soc., 21:1\u201346, 1989.","journal-title":"Bulletin of the Amer. Math. Soc."},{"unstructured":"J. Bochnak, M. Coste, and M.-F. Roy. G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Springer-Verlag, 1987.","key":"25_CR5"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0020-0190(97)00060-4","volume":"62","author":"F. Cucker","year":"1997","unstructured":"F. Cucker, P. Koiran, and M. Matamala. Complexity and dimension. Information Processing Letters, 62:209\u2013212, 1997.","journal-title":"Information Processing Letters"},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(94)00069-7","volume":"133","author":"F. Cucker","year":"1994","unstructured":"F. Cucker, M. Shub, and S. Smale. Complexity separations in Koiran\u2019s weak model. Theoretical Computer Science, 133:3\u201314, 1994.","journal-title":"Theoretical Computer Science"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/S0304-3975(00)00203-6","volume":"255","author":"H. Fournier","year":"2001","unstructured":"H. Fournier. Sparse NP-complete problems over the reals with addition. Theoretical Computer Science, 255:607\u2013610, 2001.","journal-title":"Theoretical Computer Science"},{"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.","key":"25_CR9","DOI":"10.1007\/3-540-45022-X_70"},{"key":"25_CR10","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. Comput. System Sci., 54:177\u2013189, 1997. A preliminary version appeared in 34th annual IEEE Symp. on Foundations of Computer Science, pp. 486-495, 1993.","journal-title":"J. Comput. System Sci."},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. R. Mahaney","year":"1982","unstructured":"S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. J. Comput. System Sci., 25:130\u2013143, 1982.","journal-title":"J. Comput. System Sci."},{"key":"25_CR12","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 onaP\u2260 NP result for a restricted class of real machines. Journal of Complexity, 8:451\u2013453, 1992.","journal-title":"Journal of Complexity"}],"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_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:27:52Z","timestamp":1556803672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}