{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:33Z","timestamp":1742617173773,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_64","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:17:04Z","timestamp":1330255024000},"page":"650-661","source":"Crossref","is-referenced-by-count":7,"title":["Precise average case complexity"],"prefix":"10.1007","author":[{"given":"R\u00fcdiger","family":"Reischuk","sequence":"first","affiliation":[]},{"given":"Christian","family":"Schindelhauer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"64_CR1","first-page":"193","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"S. Ben-David, B. Chor, O. Goldreich, M. Luby, On the Theory of Average Case Complexity, J. CSS 44, 1992, 193\u2013219; see also Proc. 21. STOC, 1989, 204\u2013261.","journal-title":"J. CSS"},{"key":"64_CR2","first-page":"346","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich, Average Case Completeness, J. CSS 42, 1991, 346\u2013398.","journal-title":"J. CSS"},{"key":"64_CR3","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. Levin, No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random, Proc. 31. FoCS, 1990, 812\u2013821.","DOI":"10.1109\/FSCS.1990.89604"},{"key":"64_CR4","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0196-6774(84)90032-4","volume":"5","author":"D. Johnson","year":"1984","unstructured":"D. Johnson, The NP-Completeness Column, J. of Algorithms 5, 1984, 284\u2013299.","journal-title":"J. of Algorithms"},{"key":"64_CR5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin, Average Case Complete Problems, SIAM J. Computing 15, 1986, 285\u2013286.","journal-title":"SIAM J. Computing"},{"key":"64_CR6","doi-asserted-by":"crossref","unstructured":"P. Miltersen, The Complexity of Malign Ensembles, Proc. 6. Structure in Complexity Theory, 1991, 164\u2013171.","DOI":"10.1109\/SCT.1991.160257"},{"key":"64_CR7","unstructured":"D. Mitchell, B. Selman, H. Levesque Hard and Easy Distributions of SAT Problems, Proc. 10. Nat. Conf. on Artificial Intelligence, 1992, 459\u2013465."},{"key":"64_CR8","doi-asserted-by":"crossref","unstructured":"R. Reischuk, Chr. Schindelhauer, Precise Average Case Complexity Measures, Technical Report, Technische Hochschule Darmstadt, 1992.","DOI":"10.1007\/3-540-56503-5_64"},{"key":"64_CR9","unstructured":"Chr. Schindelhauer, Neue Average Case Komplexit\u00e4tsklassen, Diplomarbeit, Technische Hochschule Darmstadt, 1991."},{"key":"64_CR10","doi-asserted-by":"crossref","unstructured":"R. Venkatesan, L. Levin, Random Instances of Graph Coloring Problems are Hard, Proc. 20. SToC, 1988, 217\u2013222.","DOI":"10.1145\/62212.62231"},{"key":"64_CR11","unstructured":"J. Wang, J. Belanger, On Average P vs. Average NP, Proc. 7. Struc. Compl., 1992."}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:50:10Z","timestamp":1742593810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}