{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:15Z","timestamp":1742617095649,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540160786"},{"type":"electronic","value":"9783540397588"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16078-7_86","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:37:38Z","timestamp":1330195058000},"page":"321-333","source":"Crossref","is-referenced-by-count":11,"title":["On sparse oracles separating feasible complexity classes"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lane","family":"Hemachandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"T. Baker, J. Gill, and R. Solovay, \u201cRelativizations of the P=?NP Question,\u201d SIAM Journal on Computing, 1975, pp. 431\u2013442.","DOI":"10.1137\/0204037"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, R. Book, T. Long, U. Sch\u00f6ning, and A. Selman, \u201cSparse Oracles and Uniform Complexity Classes,\u201d FOCS 1984, pp. 308\u2013313.","DOI":"10.1109\/SFCS.1984.715929"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer, \u201cAlternation,\u201d JACM, V. 26, #1, 1981.","DOI":"10.1145\/322234.322243"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Saxe, and M. Sipser, \u201cParity, Circuits, and the Polynomial-Time Hierarchy,\u201d FOCS 1981, pp. 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"26_CR5","unstructured":"W. Gasrarch, \u201cRecursion Theoretic Techniques in Complexity Theory and Combinatorics,\u201d Center for Research in Computing and Technology Report TR-09-85, Harvard University, May 1985."},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, \"Generalized Kolmogorov Complexity and the Structure of Feasible Computations,\u201d Cornell Department of Computer Science Technical Report TR 83-573, September 1983.","DOI":"10.1109\/SFCS.1983.21"},{"key":"26_CR7","unstructured":"J. Hartmanis, to appear in EATCS Bulletin."},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"J. Hartmanis and Y. Yesha, \u201cComputation Times of NP Sets of Different Densities,\u201d Theoretical Computer Science, V. 34, 1984, pp. 17\u201332.","journal-title":"Theoretical Computer Science"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K-I. Ko","year":"1983","unstructured":"K-I. Ko, \u201cOn Self-reducibility and Weak P-Selectivity,\u201d Journal of Computer and System Sciences, V. 26, 1983, pp. 209\u2013221.","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton, \u201cSome Connections Between Nonuniform and Uniform Complexity Classes,\u201d STOC 1980, pp. 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"S. Mahaney \u201cSparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis,\u201d FOCS 1980, pp. 54\u201360.","DOI":"10.1109\/SFCS.1980.40"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"M. Sipser, \u201cA Complexity Theoretic Approach to Randomness,\u201d STOC 1983, pp. 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"C. Wrathall, \u201cComplete Sets and the Polynomial-time Hierarchy,\u201d Theoretical Computer Science, V. 3, 1977, pp. 23\u201333.","journal-title":"Theoretical Computer Science"},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C. Yap","year":"1983","unstructured":"C. Yap, \u201cSome Consequences of Non-uniform Conditions on Uniform Classes,\u201d Theoretical Computer Science, V. 26, 1983, pp.287\u2013300.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 86"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16078-7_86.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:25:23Z","timestamp":1742588723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16078-7_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540160786","9783540397588"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-16078-7_86","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}