{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T08:09:02Z","timestamp":1749197342102},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_162","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:20:08Z","timestamp":1330244408000},"page":"449-460","source":"Crossref","is-referenced-by-count":4,"title":["On different reducibility notions for function classes"],"prefix":"10.1007","author":[{"given":"Heribert","family":"Vollmer","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I and II","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, J. Gabarr\u00f3, Structural Complexity I and II; Springer (Berlin-Heidelberg-New York, 1988 and 1990)."},{"key":"36_CR2","unstructured":"R. Beigel, Perceptrons, PP, and the polynomial time hierarchy; 7th\nStructure in Complexity Theory Conference (1992), pp. 14\u201319."},{"key":"36_CR3","unstructured":"S. A. Cook, The complexity of theorem proving procedures; 3rd\nSymposium on the Theory of Computing (1971), pp. 151\u2013158."},{"key":"36_CR4","volume-title":"Computers and Intractability: A Guide to the Theorey of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theorey of NP-Completeness; Freeman & Co. (New York, 1979)."},{"key":"36_CR5","unstructured":"J. K\u00f6bler, Strukturelle Komplexit\u00e4t von Anzahlproblemen, Dissertation, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Stuttgart, 1989."},{"key":"36_CR6","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. W. Krentel","year":"1988","unstructured":"M. W. Krentel, The complexity of optimization problems; Journal of Computer and Systems Sciences36 (1988), pp. 490\u2013509.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"36_CR7","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1145\/62.322435","volume":"31","author":"C. H. Papadimitriou","year":"1982","unstructured":"C. H. Papadimitriou, On the complexity of unique solutions; Journal of the ACM31 (1982), pp. 392\u2013400.","journal-title":"Journal of the ACM"},{"key":"36_CR8","volume-title":"Combinatorial Optimization","author":"C. H. Papadimitriou","year":"1992","unstructured":"C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization; Prentice Hall (Englewood Cliffs, New Jersey, 1992)."},{"key":"36_CR9","unstructured":"S. Toda, The complexity of finding medians; 31st\nSymposium on Foundations of Computer Science (1990), pp. 778\u2013787."},{"key":"36_CR10","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/116825.116858","volume":"38","author":"J. Tor\u00e1n","year":"1991","unstructured":"J. Tor\u00e1n, Complexity classes defined by counting quantifiers; Journal of the ACM38 (1991), pp. 753\u2013774.","journal-title":"Journal of the ACM"},{"key":"36_CR11","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant, The complexity of computing the permanent; Theoretical Computer Science8 (1979), pp. 189\u2013201.","journal-title":"Theoretical Computer Science"},{"key":"36_CR12","unstructured":"H. Vollmer, K. W. Wagner, The complexity of finding middle elements; Technical report No. 53, University W\u00fcrzburg; to appear in the International Journal of Foundations of Computer Science."},{"key":"36_CR13","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. W. Wagner","year":"1986","unstructured":"K. W. Wagner, The complexity of combinatorial problems with succinct input representation; Acta Informatica23 (1986), pp. 325\u2013356.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_162.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:08:04Z","timestamp":1619557684000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_162","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}