{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:02:45Z","timestamp":1787500965569,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_99","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:45:30Z","timestamp":1330177530000},"page":"197-217","source":"Crossref","is-referenced-by-count":15,"title":["What is a hard instance of a computational problem?"],"prefix":"10.1007","author":[{"given":"Ker-I","family":"Ko","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pekka","family":"Orponen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uwe","family":"Sch\u00f6ning","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J.L. Balc\u00e1zar","year":"1985","unstructured":"J.L. Balc\u00e1zar and U. Sch\u00f6ning, Bi-immune sets for complexity classes, Math. Systems Theory 18 (1985), 1\u201310.","journal-title":"Math. Systems Theory"},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/2455.214111","volume":"32","author":"S. Even","year":"1985","unstructured":"S. Even, A.L. Selman and Y. Yacobi, Hard core theorems for complexity classes, J. Assoc. Comput. Mach. 32 (1985), 205\u2013217.","journal-title":"J. Assoc. Comput. Mach."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24th FOCS 1983, 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"15_CR4","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0020-0190(83)90024-8","volume":"16","author":"J. Hartmanis","year":"1983","unstructured":"J. Hartmanis, On sparse sets in NP, Information Processing Letters 16 (1983), 55\u201360.","journal-title":"Information Processing Letters"},{"key":"15_CR5","unstructured":"J. Hopcroft and J. Ullman, Introduction to Automata, Lanquaqes, and Computation, Addison-Wesley, 1979."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes, Proc. 12th ACM Symp. Theory of Computing, 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"15_CR7","unstructured":"K. Ko, A definition of infinite pseudorandom sequences, manuscript, submitted for publication."},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF01699469","volume":"18","author":"K. Ko","year":"1985","unstructured":"K. Ko, Non-levelable and immune sets in the accepting density hierarchy for NP, Math. Systems Theory 18 (1985), 189\u2013205.","journal-title":"Math. Systems Theory"},{"key":"15_CR9","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"A.N. Kolmogorov, Three approaches to the quantitative definition of information, Prob. Info. Transmission 1 (1965), 1\u20137.","journal-title":"Prob. Info. Transmission"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321892.321895","volume":"22","author":"N. Lynch","year":"1975","unstructured":"N. Lynch, On reducibility to complex or sparse sets, J. Assoc. Comput. Mach. 22 (1975), 341\u2013345.","journal-title":"J. Assoc. Comput. Mach."},{"key":"15_CR11","unstructured":"A.M. Meyer and E.M. McCreight, Computationally complex and pseudo-random zero-one valued functions, in: Z. Kohavi and A.Paz (ed.), Theory of Machines and Computations, Academic Press, 1971."},{"key":"15_CR12","unstructured":"P. Orponen, A classification of complexity core lattices, manuscript, to appear."},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"P. Orponen, D. Russo and U. Sch\u00f6ning, Optimal approximations and polynomially levelable sets, SIAM Journal on Comput., to appear.","DOI":"10.1137\/0215027"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"P. Orponen and U. Sch\u00f6ning, The structure of polynomial complexity cores, Proc. 11th Symp. on Math. Found. of Comput. Sci. 1984, Lecture Notes in Computer Science 176, Springer-Verlag, 452\u2013458.","DOI":"10.1007\/BFb0030328"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"P. Orponen and U. Sch\u00f6ning, The density and complexity of polynomial cores for intractable sets, Information and Control, to appear.","DOI":"10.1016\/S0019-9958(86)80024-9"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"R.E. Wilber, Randomness and the density of hard problems, Proc. 24th FOCS 1983, 335\u2013342.","DOI":"10.1109\/SFCS.1983.49"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_99.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T17:04:22Z","timestamp":1619543062000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_99"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_99","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}