{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:08Z","timestamp":1725663068337},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_53","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:53:02Z","timestamp":1330177982000},"page":"40-49","source":"Crossref","is-referenced-by-count":0,"title":["On exponential lowness"],"prefix":"10.1007","author":[{"given":"R.","family":"Book","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Orponen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Russo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"O.","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"5_CR1","unstructured":"J. Balc\u00e1zar and R. Book, On generalized Kolmogorov complexity, STACS 86, to appear."},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, R. Book, and U. Sch\u00f6ning, Sparse oracles, lowness, and highness, SIAM J. Computing 16 (1986), to appear.","DOI":"10.1137\/0215053"},{"key":"5_CR3","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R. Book","year":"1974","unstructured":"R. Book, Tally languages and complexity classes, Info. & Control 26 (1974), 186\u2013193.","journal-title":"Info. & Control"},{"key":"5_CR4","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer, Alternation, J. Assoc. Comput. Mach. 28 (1981), 114\u2013133.","journal-title":"J. Assoc. Comput. Mach."},{"key":"5_CR5","unstructured":"M. Dekhtyar, On the relation of deterministic and nondeterministic complexity classes, Math. Found. Comput. Sci., Lecture Notes in Computer Science 45 (1977), Springer-Verlag, 282\u2013287."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"A. Goldberg and M. Sipser, Compression and ranking, Proc. 17 th ACM Sym. Theory of Computing 1985, 440\u2013448.","DOI":"10.1145\/22145.22194"},{"key":"5_CR7","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 aparse sets in NP-P, Info. Proc. Letters 16 (1983), 55\u201360.","journal-title":"Info. Proc. Letters"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24 thIEEE Sump. Foundations of Computer Science (1983), 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, V. Sewelson, and N. Immerman, Sparse sets in NP-P: EXPTIME versus NEXPTIME, Proc. 15 th ACM Symp. Theory of Computing (1983), 382\u2013391.","DOI":"10.1145\/800061.808769"},{"key":"5_CR10","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1137\/0213045","volume":"13","author":"H. Heller","year":"1984","unstructured":"H. Heller, On relativized polynomial and exponential computations, SIAM J. Computing 13 (1984), 717\u2013725.","journal-title":"SIAM J. Computing"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes, Proc. 12 th ACM Symp. Theory of Computing (1980), 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"5_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/0214003","volume":"14","author":"K. Ko","year":"1985","unstructured":"K. Ko and U. Sch\u00f6ning, On circuit-size complexity and the low hierarchy in NP, SIAM J. Computing 14 (1985), 41\u201351.","journal-title":"SIAM J. Computing"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"P. Orponen, Complexity class of alternating machines with oracles, Automata. Languages, and Programming, Lecture Notes in Computer Science 154 (1983), Springer-Verlag, 573\u2013584.","DOI":"10.1007\/BFb0036938"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning, A low and a high hierarchy in NP, J. Comput. Syst. Sci. 27 (1983), 14\u201328.","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR15","unstructured":"J. Simon, On Some Central Probems in Computational Complexity, Ph.D. dissertation, Cornell University, 1975."},{"key":"5_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"L. Stockmeyer, The polynomial-time hierarchy, Theoret. Comput. Sci. 3 (1976), 1\u201322.","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR17","unstructured":"C. Wilson, Relativization, Reducibilities, and the Exponential Hierarachy, M. Sc. thesis, Univ. of Toronto, 1980."},{"key":"5_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"C. Wrathall, Complete sets and the polylnomial-time hierarchy, Theoret. Comput. Sci. 3 (1976), 23\u201333.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16761-7_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:10:50Z","timestamp":1605625850000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}