{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:45Z","timestamp":1742617185885,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[[1994]]},"DOI":"10.1007\/3-540-57785-8_159","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:03Z","timestamp":1330262403000},"page":"415-426","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Cook versus Karp-Levin: Separating completeness notions if NP is not small"],"prefix":"10.1007","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[]},{"given":"Elvira","family":"Mayordomo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"33_CR1","unstructured":"M. Bellare and S. Goldwasser, The complexity of decision versus search, SIAM Journal on Computing, to appear. See also MIT Laboratory for Computer Science Technical Memorandum MIT\/LCS\/TM 444."},{"key":"33_CR2","doi-asserted-by":"crossref","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 (1977), pp. 305\u2013322.","journal-title":"SIAM Journal on Computing"},{"key":"33_CR3","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R. V. Book","year":"1974","unstructured":"R. V. Book, Tally languages and complexity classes, Information and Control 26 (1974), pp. 186\u2013193.","journal-title":"Information and Control"},{"key":"33_CR4","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02090397","volume":"24","author":"H. Buhrman","year":"1991","unstructured":"H. Buhrman, S. Homer, and L. Torenvliet, Completeness for nondeterministic complexity classes, Mathematical Systems Theory 24 (1991), pp. 179\u2013200.","journal-title":"Mathematical Systems Theory"},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem proving procedures, Proceedings of the Third ACM Symposium on the Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"S. Homer, Structural properties of nondeterministic complete sets, Proceedings of the Fifth Annual Structure in Complexity Theory Conference, 1990, pp. 3\u201310.","DOI":"10.1109\/SCT.1990.113949"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"D. W. Juedes and J. H. Lutz, The complexity and distribution of hard problems, Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 177\u2013185. SIAM Journal on Computing, to appear.","DOI":"10.1109\/SFCS.1993.366869"},{"key":"33_CR8","doi-asserted-by":"crossref","unstructured":"R. M. Karp, Reducibility among combinatorial problems, In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pp. 85\u2013104. Plenum Press, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"33_CR9","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/0210061","volume":"10","author":"K. Ko","year":"1981","unstructured":"K. Ko and D. Moore, Completeness, approximation and density, SIAM Journal on Computing 10 (1981), pp. 787\u2013796.","journal-title":"SIAM Journal on Computing"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, and A. Selman, A comparison of polynomial-time reducibilities, Theoretical Computer Science 1 (1975), pp. 103\u2013123.","journal-title":"Theoretical Computer Science"},{"key":"33_CR11","first-page":"265","volume":"9","author":"L. A. Levin","year":"1973","unstructured":"L. A. Levin, Universal sequential search problems, Problems of Information Transmission 9 (1973), pp. 265\u2013266.","journal-title":"Problems of Information Transmission"},{"key":"33_CR12","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/0022-0000(90)90026-H","volume":"41","author":"L. Longpr\u00e9","year":"1990","unstructured":"L. Longpr\u00e9 and P. Young, Cook reducibility is faster than Karp reducibility in NP, Journal of Computer and System Sciences 41 (1990), pp. 389\u2013401.","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR13","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. H. Lutz","year":"1992","unstructured":"J. H. Lutz, Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences 44 (1992), pp. 220\u2013258.","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR14","unstructured":"J. H. Lutz, Resource-bounded measure, in preparation."},{"key":"33_CR15","unstructured":"J. H. Lutz and E. Mayordomo, Measure, stochasticity, and the density of hard languages, SIAM Journal on Computing, to appear."},{"key":"33_CR16","doi-asserted-by":"crossref","unstructured":"E. Mayordomo, Almost every set in exponential time is P-bi-immune, Seventeenth International Symposium on Mathematical Foundations of Computer Science, 1992, pp. 392\u2013400. Springer-Verlag. Theoretical Computer Science, to appear.","DOI":"10.1007\/3-540-55808-X_38"},{"key":"33_CR17","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"A. R. Meyer","year":"1977","unstructured":"A. R. Meyer, 1977, reported in [2].","journal-title":"SIAM Journal on Computing"},{"key":"33_CR18","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and O. Watanabe, On polynomial bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing 20 (1991), pp. 471\u2013483.","journal-title":"SIAM Journal on Computing"},{"key":"33_CR19","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0019-9958(86)80024-9","volume":"70","author":"P. Orponen","year":"1986","unstructured":"P. Orponen and U. Sch\u00f6ning, The density and complexity of polynomial cores for intractable sets, Information and Control 70 (1986), pp. 54\u201368.","journal-title":"Information and Control"},{"key":"33_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00538763","volume":"16","author":"C. P. Schnorr","year":"1970","unstructured":"C. P. Schnorr, Klassifikation der Zufallsgesetze nach Komplexit\u00e4t und Ordnung, Z. Wahrscheinlichkeitstheorie verw. Geb. 16 (1970), pp. 1\u201321.","journal-title":"Z. Wahrscheinlichkeitstheorie verw. Geb."},{"key":"33_CR21","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C. P. Schnorr","year":"1971","unstructured":"C. P. Schnorr, A unified approach to the definition of random sequences, Mathematical Systems Theory 5 (1971), pp. 246\u2013258.","journal-title":"Mathematical Systems Theory"},{"key":"33_CR22","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr, Zuf\u00e4lligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics 218 (1971).","DOI":"10.1007\/BFb0112458"},{"key":"33_CR23","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. P. Schnorr","year":"1973","unstructured":"C. P. Schnorr, Process complexity and effective random tests, Journal of Computer and System Sciences 7 (1973), pp. 376\u2013388.","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. L. Selman","year":"1979","unstructured":"A. L. Selman, P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP, Mathematical Systems Theory 13 (1979), pp. 55\u201365.","journal-title":"Mathematical Systems Theory"},{"key":"33_CR25","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(82)90039-1","volume":"19","author":"A. L. Selman","year":"1982","unstructured":"A. L. Selman, Reductions on NP and P-selective sets, Theoretical Computer Science 19 (1982), pp. 287\u2013304.","journal-title":"Theoretical Computer Science"},{"key":"33_CR26","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"O. Watanabe, A comparison of polynomial time completeness notions, Theoretical Computer Science 54 (1987), pp. 249\u2013265.","journal-title":"Theoretical Computer Science"},{"key":"33_CR27","unstructured":"O. Watanabe, On the Structure of Intractable Complexity Classes, PhD thesis, Tokyo Institute of Technology, 1987."},{"key":"33_CR28","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0304-3975(92)90074-P","volume":"97","author":"O. Watanabe","year":"1992","unstructured":"O. Watanabe and S. Tang, On polynomial time Turing and many-one completeness in PSPACE, Theoretical Computer Science 97 (1992), pp. 199\u2013215.","journal-title":"Theoretical Computer Science"},{"key":"33_CR29","doi-asserted-by":"crossref","unstructured":"P. Young, Some structural properties of polynomial reducibilities and sets in NP, Proceedings of the Fifteenth ACM Symposium on Theory of Computing, 1983, pp. 392\u2013401.","DOI":"10.1145\/800061.808770"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_159","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:12:50Z","timestamp":1742595170000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_159"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_159","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}