{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:07:50Z","timestamp":1742947670370,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319500614"},{"type":"electronic","value":"9783319500621"}],"license":[{"start":{"date-parts":[[2016,12,1]],"date-time":"2016-12-01T00:00:00Z","timestamp":1480550400000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-50062-1_8","type":"book-chapter","created":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T10:09:42Z","timestamp":1480500582000},"page":"115-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity with Rod"],"prefix":"10.1007","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,1]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0304-3975(02)00810-1","volume":"298","author":"R Downey","year":"2003","unstructured":"Downey, R., Fortnow, L.: Uniformly hard languages. Theor. Comput. Sci. 298(2), 303\u2013315 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Fortnow, L.: Kolmogorov complexity. In: Downey, R., Hirschfeldt, D. (eds.) Aspects of Complexity, Minicourses in Algorithmics, Complexity, and Computational Algebra, NZMRI Mathematics Summer Meeting. de Gruyter Series in Logic and Its Applications, Kaikoura, New Zealand, 7\u201315 January 2000, vol. 4. de Gruyter (2001)","DOI":"10.1515\/9783110889178.73"},{"key":"8_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic Randomness and Complexity","author":"R Downey","year":"2010","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer Science & Business Media, Heidelberg (2010)"},{"issue":"1","key":"8_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"8_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H Bodlaender","year":"2009","unstructured":"Bodlaender, H., Downey, R., Fellows, M., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"8_CR6","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/060668092","volume":"39","author":"D Harnik","year":"2010","unstructured":"Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. SIAM J. Comput. 39(5), 1667\u20131713 (2010)","journal-title":"SIAM J. Comput."},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Hitchcock, J.: NP-hard sets are exponentially dense unless coNP is contained in NP\/poly. In: 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, pp. 1\u20137. IEEE, New York, June 2008","DOI":"10.1109\/CCC.2008.21"},{"issue":"5","key":"8_CR8","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/130927115","volume":"44","author":"A Drucker","year":"2015","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. SIAM J. Comput. 44(5), 1443\u20131479 (2015)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"8_CR9","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E Post","year":"1944","unstructured":"Post, E.: Recursively enumerable sets of positive integers and their decision problems. Bullet. Am. Math. Soc. 50(5), 284\u2013316 (1944)","journal-title":"Bullet. Am. Math. Soc."},{"key":"8_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"R Soare","year":"1987","unstructured":"Soare, R.: Recursively Enumerable Sets and Degrees. Springer, Berlin (1987)"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Cook, S.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd ACM Symposium on the Theory of Computing, pp. 151\u2013158. ACM, New York (1971)","DOI":"10.1145\/800157.805047"},{"key":"8_CR12","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, New York (1972). doi:10.1007\/978-1-4684-2001-2_9"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R Ladner","year":"1975","unstructured":"Ladner, R.: On the structure of polynomial time reducibility. J. ACM 22, 155\u2013171 (1975)","journal-title":"J. ACM"},{"key":"8_CR14","first-page":"569","volume-title":"Robust Simulations and Significant Separations","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Robust Simulations and Significant Separations, pp. 569\u2013580. Springer, Heidelberg (2011)"},{"key":"8_CR15","unstructured":"Fortnow, L., Santhanam, R.: New non-uniform lower bounds for uniform classes. In: Raz, R. (ed.) 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 50, pp. 19:1\u201319:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016)"}],"container-title":["Lecture Notes in Computer Science","Computability and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-50062-1_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:55:22Z","timestamp":1709830522000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-50062-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,1]]},"ISBN":["9783319500614","9783319500621"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-50062-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016,12,1]]},"assertion":[{"value":"1 December 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}