{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:23Z","timestamp":1725664463280},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_28","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:14Z","timestamp":1330290254000},"page":"331-343","source":"Crossref","is-referenced-by-count":2,"title":["Fine separation of average time complexity classes"],"prefix":"10.1007","author":[{"given":"Jin -yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. Balc\u00e1zar","year":"1985","unstructured":"J. Balc\u00e1zar and U. Sch\u00f6ning. Bi-immune sets for complexity classes. Mathematical Systems Theory, 18:1\u201310, 1985.","journal-title":"Mathematical Systems Theory"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"J. Belanger and J. Wang. Rankable distributions do not provide harder instances than uniform distributions. Manuscript, 1995.","DOI":"10.1007\/BFb0030860"},{"issue":"2","key":"28_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0022-0000(92)90019-F","volume":"44","author":"S. Ben-Dav\u00edd","year":"1992","unstructured":"S. Ben-Dav\u00edd, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity. J. Computer System Sci., 44(2):193\u2013219, 1992.","journal-title":"J. Computer System Sci."},{"key":"28_CR4","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S. Cook","year":"1973","unstructured":"S. Cook and R. Reckow. Time bounded random access machines. J. Comput. System Sci., 7:354\u2013375, 1973.","journal-title":"J. Comput. System Sci."},{"key":"28_CR5","unstructured":"J. Geske, D. Huynh, and A. Selman. A hierarchy theorem for almost every-where complex sets with application to polynomial complexity degrees. In STACS 1987, 1987."},{"issue":"1","key":"28_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0890-5401(91)90022-T","volume":"92","author":"J. Geske","year":"1991","unstructured":"J. Geske, D. Huynh, and J. Seiferas. A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes. Inf. and Comput., 92(1):97\u2013104, 1991.","journal-title":"Inf. and Comput."},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich. Average case completeness. J. Comput. System Sci., 42:346\u2013398, 1991.","journal-title":"J. Comput. System Sci."},{"key":"28_CR8","volume-title":"Cambridge Tracts in Mathematics and Mathematical Physics","author":"G. Hardy","year":"1924","unstructured":"G. Hardy. Orders of Infinity, The \u2018infinit\u00e4rcalc\u00fcl\u2019 of Paul du Bois-Reymond, volume 12 of Cambridge Tracts in Mathematics and Mathematical Physics. Cambridge University Press, London, 2nd edition, 1924.","edition":"2nd edition"},{"key":"28_CR9","first-page":"54","volume":"10","author":"G. Hardy","year":"1911","unstructured":"G. Hardy. Properties of logarithmico-exponential functions. Proc. London Math. Soc., (2),10:54\u201390, 1911.","journal-title":"Proc. London Math. Soc., (2)"},{"key":"28_CR10","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285\u2013306, 1965.","journal-title":"Trans. Amer. Math. Soc."},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01744572","volume":"16","author":"K. Ko","year":"1983","unstructured":"K. Ko. On the definition of some complexity classes of real numbers. Math. Systems Theory, 16:95\u2013109, 1983.","journal-title":"Math. Systems Theory"},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin. Average case complete problems. SIAM J. of Comput., 15:285\u2013286, 1986.","journal-title":"SIAM J. of Comput."},{"key":"28_CR13","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0020-0190(92)90138-L","volume":"42","author":"M. Li","year":"1992","unstructured":"M. Li and P. Vit\u00e1nyi. Average case complexity under the universal distribution equals worst-case complexity. Inf. Proc. Lett., 42:145\u2013149, 1992.","journal-title":"Inf. Proc. Lett."},{"key":"28_CR14","first-page":"415","volume":"775","author":"J. Lutz","year":"1994","unstructured":"J. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. In Proc. 11th Annual Symp. on Theor. Aspects of Com. Sci., Lecture Notes in Computer Science, Springer-Verlag, 775:415\u2013426, 1994.","journal-title":"Proc. 11th Annual Symp. on Theor. Aspects of Com. Sci., Lecture Notes in Computer Science, Springer-Verlag"},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/0304-3975(94)00023-C","volume":"136","author":"E. Mayordomo","year":"1994","unstructured":"E. Mayordomo. Almost every set in exponential time is P-bi-immune. Theoret. Comput. Sci., 136:487\u2013506, 1994.","journal-title":"Theoret. Comput. Sci."},{"key":"28_CR16","unstructured":"C. Rackoff. Personal communication."},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"R. Reishuk and C. Schindelhauer Precise average case complexity. In Proc. 10th Annual Symp. on Theoretical Aspects of Computer Sci. v. 665 of Lecture Notes in Computer Sci., pages 650\u2013661. Springer Verlag. 1993.","DOI":"10.1007\/3-540-56503-5_64"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"R. Schuler and T. Yamakami Sets computable in polynomial time on the average. In Proc. First Annual Conf. on Computing and Combinatorics v. 959 of Lecture Notes in Computer Sci., pages 400\u2013409. Springer Verlag. 1995.","DOI":"10.1007\/BFb0030859"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:28:07Z","timestamp":1619573287000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}