{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:57:03Z","timestamp":1725544623726},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_36","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T08:27:54Z","timestamp":1141115274000},"page":"444-454","source":"Crossref","is-referenced-by-count":4,"title":["Redundancy in Complete Sets"],"prefix":"10.1007","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[]},{"given":"Liyu","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: 17th Annual IEEE Conference on Computational Complexity, pp. 139\u2013145 (2002)","DOI":"10.1109\/CCC.2002.1004349"},{"key":"36_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0048934","volume-title":"Programming Languages and their Definition","author":"K. Ambos-Spies","year":"1984","unstructured":"Ambos-Spies, K.: P-mitotic sets. In: B\u00f6rger, E., Hasenj\u00e4ger, G., Roding, D. (eds.) Programming Languages and their Definition. LNCS, vol.\u00a0177, pp. 1\u201323. Springer, Heidelberg (1984)"},{"issue":"1","key":"36_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. Balc\u00e1zar","year":"1985","unstructured":"Balc\u00e1zar, J., Sch\u00f6ning, U.: Bi-immune sets for complexity classes. Mathematical Systems Theory\u00a018(1), 1\u201310 (1985)","journal-title":"Mathematical Systems Theory"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01276436","volume":"2","author":"R. Beigel","year":"1992","unstructured":"Beigel, R., Feigenbaum, J.: On being incoherent without being very hard. Computational Complexity\u00a02, 1\u201317 (1992)","journal-title":"Computational Complexity"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM Journal on Computing\u00a06, 305\u2013322 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"36_CR6","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1137\/S0097539798334736","volume":"29","author":"H. Buhrman","year":"2000","unstructured":"Buhrman, H., Fortnow, L., van Melkebeek, D., Torenvliet, L.: Separating complexity classes using autoreducibility. SIAM Journal on Computing\u00a029(5), 1497\u20131520 (2000)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"36_CR7","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1137\/S0097539798334736","volume":"29","author":"H. Buhrman","year":"2000","unstructured":"Buhrman, H., Fortnow, L., van Melkebeek, D., Torenvliet, L.: Using autoreducibility to separate complexity classes. SIAM Journal on Computing\u00a029(5), 1497\u20131520 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1137\/S0097539795279724","volume":"27","author":"H. Buhrman","year":"1998","unstructured":"Buhrman, H., Hoene, A., Torenvliet, L.: Splittings, robustness, and structure of complete sets. SIAM Journal on Computing\u00a027, 637\u2013653 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Torenvliet, L.: On the structure of complete sets. In: Proceedings 9th Structure in Complexity Theory, pp. 118\u2013133 (1994)","DOI":"10.1109\/SCT.1994.315811"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Torenvliet, L.: Separating complexity classes using structural properties. In: Proceedings of the 19th IEEE Conference on Computational Complexity, pp. 130\u2013138 (2004)","DOI":"10.1109\/CCC.2004.1313820"},{"key":"36_CR11","first-page":"41","volume":"85","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Torenvliet, L.: A Post\u2019s program for complexity theory. Bulleting of the EATCS\u00a085, 41\u201351 (2005)","journal-title":"Bulleting of the EATCS"},{"key":"36_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/11549345_34","volume-title":"Mathematical Foundations of Computer Science 2005","author":"C. Gla\u00dfer","year":"2005","unstructured":"Gla\u00dfer, C., Ogihara, M., Pavan, A., Selman, A.L., Zhang, L.: Autoreducibility, mitoticity, and immunity. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 387\u2013398. Springer, Heidelberg (2005)"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer, C., Ogihara, M., Pavan, A., Selman, A.L., Zhang, L.: Autoreducibility, mitoticity, and immunity. Technical Report TR05-11, ECCC (2005)","DOI":"10.1007\/11549345_34"},{"key":"36_CR14","unstructured":"Gla\u00dfer, C., Pavan, A., Selman, A.L., Zhang, L.: Redundancy in complete sets. Technical Report 05-068, Electronic Colloquium on Computational Complexity (ECCC) (2005)"},{"issue":"2","key":"36_CR15","doi-asserted-by":"publisher","first-page":"199","DOI":"10.2307\/2272056","volume":"38","author":"R. Ladner","year":"1973","unstructured":"Ladner, R.: Mitotic recursively enumerable sets. Journal of Symbolic Logic\u00a038(2), 199\u2013211 (1973)","journal-title":"Journal of Symbolic Logic"},{"issue":"2","key":"36_CR16","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"Mahaney, S.: Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and Systems Sciences\u00a025(2), 130\u2013143 (1982)","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"3","key":"36_CR17","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"Ogiwara, M., Watanabe, O.: On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal of Computing\u00a020(3), 471\u2013483 (1991)","journal-title":"SIAM Journal of Computing"},{"key":"#cr-split#-36_CR18.1","unstructured":"Trakhtenbrot, B.: On autoreducibility. Dokl. Akad. Nauk SSSR??192 (1970);"},{"key":"#cr-split#-36_CR18.2","unstructured":"Translation in Soviet Math. Dokl. 11, 814??? 817 (1970)"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Yao, A.: Coherent functions and program checkers. In: Proceedings of the 22n Annual Symposium on Theory of Computing, pp. 89\u201394 (1990)","DOI":"10.1145\/100216.100226"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T03:31:38Z","timestamp":1555471898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11672142_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}