{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:39Z","timestamp":1725511779223},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_22","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"248-259","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Unions of Disjoint Sets"],"prefix":"10.1007","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Travers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","first-page":"139","volume-title":"IEEE Conference on Computational Complexity","author":"M. Agrawal","year":"2002","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: IEEE Conference on Computational Complexity, pp. 139\u2013147. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"22_CR2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Logic and Machines: Decision Problems and Complexity","author":"K. Ambos-Spies","year":"1984","unstructured":"Ambos-Spies, K.: P-mitotic sets. In: B\u00f6rger, E., R\u00f6dding, D., Hasenjaeger, G. (eds.) Rekursive Kombinatorik 1983. LNCS, vol.\u00a0171, pp. 1\u201323. Springer, Heidelberg (1984)"},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"82","author":"A. Blass","year":"1982","unstructured":"Blass, A., Gurevich, Y.: On the unique satisfiability problem. Information and Control\u00a082, 80\u201388 (1982)","journal-title":"Information and Control"},{"key":"22_CR4","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"},{"key":"22_CR5","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":"22_CR6","unstructured":"Boneh, D., Venkatesan, R.: Rounding in lattices and its cryptographic applications. In: SODA, pp. 675\u2013681 (1997)"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01768464","volume":"11","author":"R.V. Book","year":"1977","unstructured":"Book, R.V., et al.: Inclusion complete tally languages and the hartmanis-berman conjecture. Mathematical Systems Theory\u00a011, 1\u20138 (1977)","journal-title":"Mathematical Systems Theory"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J.-Y. Cai","year":"1988","unstructured":"Cai, J.-Y., et al.: The boolean hierarchy I: Structural properties. SIAM Journal on Computing\u00a017, 1232\u20131252 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"22_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0304-3975(02)00810-1","volume":"298","author":"R.G. Downey","year":"2003","unstructured":"Downey, R.G., Fortnow, L.: Uniformly hard languages. Theoretical Computer Science\u00a0298(2), 303\u2013315 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"3-4","key":"22_CR10","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s00037-002-0173-4","volume":"11","author":"L. Fortnow","year":"2002","unstructured":"Fortnow, L., Rogers, J.: Separability and one-way functions. Computational Complexity\u00a011(3-4), 137\u2013157 (2002)","journal-title":"Computational Complexity"},{"key":"22_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/11672142_36","volume-title":"STACS 2006","author":"C. Gla\u00dfer","year":"2006","unstructured":"Gla\u00dfer, C., et al.: Redundancy in complete sets. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 444\u2013454. Springer, Heidelberg (2006)"},{"issue":"2","key":"22_CR12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.L.: Complexity measures for public-key cryptosystems. SIAM Journal on Computing\u00a017(2), 309\u2013335 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/11821069_38","volume-title":"Mathematical Foundations of Computer Science 2006","author":"C. Gla\u00dfer","year":"2006","unstructured":"Gla\u00dfer, C., Travers, S.: Machines that can output empty words. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 436\u2013446. Springer, Heidelberg (2006)"},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BFb0016264","volume-title":"Mathematical Foundations of Computer Science 1986","author":"T. Gundermann","year":"1986","unstructured":"Gundermann, T., Wechsung, G.: Nondeterministic Turing machines with modified acceptance. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol.\u00a0233, pp. 396\u2013404. Springer, Heidelberg (1986)"},{"key":"22_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/11786986_41","volume-title":"Automata, Languages and Programming","author":"J. Hitchcock","year":"2006","unstructured":"Hitchcock, J., Pavan, A.: Comparing reductions to NP-complete sets. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 465\u2013476. Springer, Heidelberg (2006)"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U.: High sets for NP. In: Advances in Algorithms, Languages, and Complexity, pp. 139\u2013156 (1997)","DOI":"10.1007\/978-1-4613-3394-4_6"},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Wagner, K.W.: The difference and the truth-table hierarchies for NP. RAIRO Inform. Th\u00e9or.\u00a021, 419\u2013435 (1987)","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E., Lynch, N.A., Selman, A.L.: A comparison of polynomial time reducibilities. Theoretical Computer Science\u00a01, 103\u2013123 (1975)","journal-title":"Theoretical Computer Science"},{"key":"22_CR19","unstructured":"Long, T.J.: On some Polynomial Time Reducibilities. PhD thesis, Purdue University, Lafayette, Ind. (1978)"},{"issue":"1","key":"22_CR20","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"Sch\u00f6ning, U.: A low and a high hierarchy within NP. Journal of Computer and System Sciences\u00a027(1), 14\u201328 (1983)","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A.L. Selman","year":"1979","unstructured":"Selman, A.L.: P-selective sets, tally languages, and the behavior of polynomial-time reducibilities on NP. Mathematical Systems Theory\u00a013, 55\u201365 (1979)","journal-title":"Mathematical Systems Theory"},{"issue":"5","key":"22_CR22","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/0217062","volume":"17","author":"A.L. Selman","year":"1988","unstructured":"Selman, A.L.: Natural self-reducible sets. SIAM Journal on Computing\u00a017(5), 989\u2013996 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR23","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L.G. Valiant","year":"1976","unstructured":"Valiant, L.G.: Relative complexity of checking and evaluation. Information Processing Letters\u00a05, 20\u201323 (1976)","journal-title":"Information Processing Letters"},{"key":"22_CR24","series-title":"Lecture Notes in Computer Science","first-page":"485","volume-title":"Fundamentals of Computation Theory","author":"K.W. Wagner","year":"1985","unstructured":"Wagner, K.W., Wechsung, G.: On the boolean closure of NP. In: Budach, L. (ed.) FCT 1985. LNCS, vol.\u00a0199, pp. 485\u2013493. Springer, Heidelberg (1985)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:11:48Z","timestamp":1605762708000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_22","relation":{},"subject":[]}}