{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:48Z","timestamp":1742617128668,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540544876"},{"type":"electronic","value":"9783540384014"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54487-9_72","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:55:08Z","timestamp":1330210508000},"page":"389-399","source":"Crossref","is-referenced-by-count":5,"title":["The gap-language-technique revisited"],"prefix":"10.1007","author":[{"given":"Heribert","family":"Vollmer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"24_CR1","first-page":"95","volume-title":"Trends in Theoretical Computer Science","author":"K. Ambos-Spies","year":"1988","unstructured":"K. Ambos-Spies, Polynomial time degrees of NP-sets; in: E. B\u00f6rger, Trends in Theoretical Computer Science, Computer Science Press, Rockville 1988, 95\u2013142."},{"key":"24_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, J. Gabarr\u00f3, Structural Complexity I; Springer, Berlin, 1988."},{"doi-asserted-by":"crossref","unstructured":"R. Book, D.-Z. Du, D. Russo, On polynomial and generalized complexity cores; Proc. 3rd Structure (1988), 236\u2013250.","key":"24_CR3","DOI":"10.1109\/SCT.1988.5283"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. K. Chandra","year":"1984","unstructured":"A. K. Chandra, L. Stockmeyer, U. Vishkin, Constant depth reducibility; SIAM J. Comput. (13) (1984), 423\u2013439.","journal-title":"SIAM J. Comput."},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0022-0000(81)90021-0","volume":"22","author":"P. Chew","year":"1981","unstructured":"P. Chew, M. Machtey, A note on structure and looking back applied to the relative complexity of computable functions; J. Comput. System Sci.22 (1981), 53\u201359.","journal-title":"J. Comput. System Sci."},{"key":"24_CR6","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook, A taxonomy of problems with fast parallel Algorithms; Inf. & Contr. 64 (1985), 2\u201322.","journal-title":"Inf. & Contr."},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"16","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, On the structure of polynomial time reducibility, J. ACM16 (1975), 155\u2013171.","journal-title":"J. ACM"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"L. H. Landweber","year":"1975","unstructured":"L. H. Landweber, R. J. Lipton, E. L. Robertson, On the structure of sets in NP and other complexity classes; Theoret. Comput. Sci.1 (1975), 103\u2013123.","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR9","doi-asserted-by":"publisher","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.ACM22 (1975), 341\u2013345.","journal-title":"J.ACM"},{"key":"24_CR10","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0019-9958(86)80024-9","volume":"70","author":"P. Orponen","year":"1986","unstructured":"P. Orponen, U. Sch\u00f6ning, The density and complexity of polynomial cores for intractable sets; Inf. & Contr.70 (1986), 54\u201368.","journal-title":"Inf. & Contr."},{"key":"24_CR11","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"H. Rogers Jr., Theory of Recursive Functions and Effective Computability; McGraw-Hill, New York, 1967."},{"key":"24_CR12","volume-title":"Recursively Enumerable Sets and Degrees","author":"R. I. Soare","year":"1986","unstructured":"R. I. Soare, Recursively Enumerable Sets and Degrees; Springer, Berlin, 1986."},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(82)90114-1","volume":"18","author":"U. Sch\u00f6ning","year":"1982","unstructured":"U. Sch\u00f6ning, A uniform approach to obtain diagonal sets in complexity classes; Theoret. Comput. Sci.18 (1982), 95\u2013103.","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0304-3975(84)90124-5","volume":"31","author":"U. Sch\u00f6ning","year":"1984","unstructured":"U. Sch\u00f6ning, Minimal pairs for P, Theoret. Comput. Sci.31 (1984), 41\u201348.","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(85)90217-8","volume":"38","author":"D. Schmidt","year":"1985","unstructured":"D. Schmidt, The recursion-theoretic structure of complexity classes; Theoret. Comput. Sci.38 (1985), 143\u2013156.","journal-title":"Theoret. Comput. Sci."},{"unstructured":"M. Serna, The parallel approximability of P-complete problems; Tesis doctoral, Facultat d'Inform\u00e0tica de Barcelona (1990).","key":"24_CR16"},{"unstructured":"J. Tor\u00e1n, Structural properties of the counting hierarchies; Tesis doctoral, Facultat d'Inform\u00e0tica de Barcelona (1988).","key":"24_CR17"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54487-9_72.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:19:53Z","timestamp":1742591993000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54487-9_72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544876","9783540384014"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-54487-9_72","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}