{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:36Z","timestamp":1725663696204},"publisher-location":"Berlin, Heidelberg","reference-count":18,"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_151","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:19:36Z","timestamp":1330262376000},"page":"313-324","source":"Crossref","is-referenced-by-count":3,"title":["NCk(NP)=AC k\u22121(NP)"],"prefix":"10.1007","author":[{"given":"Mitsunori","family":"Ogiwara","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender and C. Wilson. Width-bounded reducibility and binary search over complexity classes. In Proceedings of the 5th Conference on Structure in Complexity Theory, pages 122\u2013129. IEEE Computer Society Press, 1990.","DOI":"10.1109\/SCT.1990.113961"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"C. Alvarez, J. Balcazar, and B. Jenner. Functional oracle queries as a measure of parallel time. In Proceedings of the 8th Symposium on Theoretical Aspects of Computer Science, pages 422\u2013433. Springer-Verlag Lecture Notes in Computer Science #480, 1991.","DOI":"10.1007\/BFb0020817"},{"issue":"4","key":"25_CR3","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"A. Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6(4):733\u2013744, December 1977.","journal-title":"SIAM Journal on Computing"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"S. Buss and L. Hay. On truth-table reducibility to SAT and the difference hierarchy over NP. In Proceedings of the 3rd Conference on Structure in Complexity Theory, pages 224\u2013233. IEEE Computer Society Press, 1988.","DOI":"10.1109\/SCT.1988.5282"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"J. Castro and C. Seara. Characterizations of some complexity classes between \u03b82\/p and \u03b42\/p. In Proceedings of the 9th Symposium on Theoretical Aspects of Computer Science, pages 305\u2013317. Springer-Verlag Lecture Notes in Computer Science #577, 1992.","DOI":"10.1007\/3-540-55210-3_192"},{"issue":"2","key":"25_CR6","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"A. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2):423\u2013439, May 1984.","journal-title":"SIAM Journal on Computing"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"S. Cook. The complexity of theorem proving procedures. In Proceedings of the 3rd Symposium on Theory of Computing, pages 151\u2013158. ACM Press, 1971.","DOI":"10.1145\/800157.805047"},{"key":"25_CR8","first-page":"2","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook. A taxonomy of problems with fast parallel algorithms. Information and Computation, 64:2\u201322, 1985.","journal-title":"Information and Computation"},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17:13\u201327, 1984.","journal-title":"Mathematical Systems Theory"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"G. Gottlob. NP trees and Carnap's modal logic. In Proceedings of the 34th Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1993. to appear.","DOI":"10.1109\/SFCS.1993.366883"},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"R. Ladner and N. Lynch. Relativization of questions about logspace computability. Mathematical Systems Theory, 10:19\u201332, 1976.","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"25_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"l","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, l(2):103\u2013123, 1975.","journal-title":"Theoretical Computer Science"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"M. Ogiwara. Generalized theorems on the relationships among reducibility notions to certain complexity classes. Mathematical Systems Theory. to appear.","DOI":"10.1007\/BF01578841"},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"K. Wagner. The complexity of combinatorial problems with succinct input representation. Acta Informatica, 23:325\u2013356, 1986.","journal-title":"Acta Informatica"},{"issue":"5","key":"25_CR15","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"K. Wagner. Bounded query classes. SIAM Journal on Computing, 19(5):833\u2013846, October 1990.","journal-title":"SIAM Journal on Computing"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. Wilson","year":"1985","unstructured":"C. Wilson. Relatizived circuit complexity. Journal of Computer and System Science, 31:169\u2013181, 1985.","journal-title":"Journal of Computer and System Science"},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01692056","volume":"20","author":"C. Wilson","year":"1987","unstructured":"C. Wilson. Relatizived NC. Mathematical Systems Theory, 20:13\u201329, 1987.","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"25_CR18","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/0219024","volume":"19","author":"C. Wilson","year":"1990","unstructured":"C. Wilson. On the decomposability of NC and AC. SIAM Journal on Computing, 19(2):384\u2013296, April 1990.","journal-title":"SIAM Journal on Computing"}],"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_151.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:58Z","timestamp":1605647638000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_151","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}