{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:25Z","timestamp":1742617225587,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540613329"},{"type":"electronic","value":"9783540684619"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61332-3_159","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:33:56Z","timestamp":1330292036000},"page":"260-267","source":"Crossref","is-referenced-by-count":0,"title":["The join can lower complexity"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"Zhigen","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"A. Amir, R. Beigel, and W. Gasarch. Some connections between bounded query classes and non-uniform complexity. Manuscript, July 11, 1994. A preliminary version appeared in Proceedings of the 5th Structure in Complexity Theory Conference, pages 232\u2013243. IEEE Computer Society Press, 1990.","DOI":"10.1109\/SCT.1990.113971"},{"issue":"1","key":"27_CR2","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1145\/147508.147546","volume":"39","author":"E. Allender","year":"1992","unstructured":"E. Allender and L. Hemachandra. Lower bounds for the low hierarchy. Journal of the ACM, 39(1):234\u2013251, 1992.","journal-title":"Journal of the ACM"},{"issue":"3","key":"27_CR3","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1137\/0215053","volume":"15","author":"J. Balc\u00e1zar","year":"1986","unstructured":"J. Balc\u00e1zar, R. Book, and U. Sch\u00f6ning. Sparse sets, lowness and highness. SIAM Journal on Computing, 15(3):739\u2013746, 1986.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"27_CR4","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/156063.156064","volume":"24","author":"L. Hemaspaandra","year":"1993","unstructured":"L. Hemaspaandra. Lowness: a yardstick for NP \u2014 P. SIGACT News, 24(2):10\u201314, 1993.","journal-title":"SIGACT News"},{"issue":"1","key":"27_CR5","first-page":"66","volume":"1","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra and Z. Jiang. P-Selectivity: Intersections and Indices. Theoretical Computer Science, to appear. A priliminary version has also appeared in: Journal on Computing and Information, 1(1):66\u201375, 1995. Special Issue: Proceedings of the 6th International Conference on Computing and Information, May 1994.","journal-title":"A priliminary version has also appeared in: Journal on Computing and Information"},{"key":"27_CR6","series-title":"Technical Report TR","volume-title":"Multi-selectivity and complexity-lowering joins","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe. Multi-selectivity and complexity-lowering joins. Technical Report TR 568, University of Rochester, Rochester, NY, 1995."},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman. Computing solutions uniquely collapses the polynomial hierarchy. To appear in SIAM Journal on Computing. A preliminary version appeared in Proc. 5th ISAAC, pages 56\u201364, 1994.","DOI":"10.1007\/3-540-58325-4_166"},{"key":"27_CR8","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing, pages 302\u2013309, April 1980. An extended version has also appeared as: Turing machines that take advice. L'Enseignement Math\u00e9matique, 2nd series, 28: 191\u2013209, 1982."},{"key":"27_CR9","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0890-5401(91)90002-J","volume":"90","author":"K. Ko","year":"1991","unstructured":"K. Ko. Separating the low and the high hierarchies by oracles. Information and Computation, 90:156\u2013177, 1991.","journal-title":"Information and Computation"},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(94)00016-6","volume":"134","author":"J. K\u00f6bler","year":"1994","unstructured":"J. K\u00f6bler. Locating P\/poly optimally in the extended low hierarchy. Theoretical Computer Science, 134:263\u2013285, 1994.","journal-title":"Theoretical Computer Science"},{"key":"27_CR11","unstructured":"J. K\u00f6bler. On the structure of low sets. In Proceedings of the 10th Structure in Complexity Theory Conference, pages 246\u2013261. IEEE Computer Society Press, 1995."},{"issue":"1","key":"27_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/0214003","volume":"14","author":"K. Ko","year":"1985","unstructured":"K. Ko and U. Sch\u00f6ning. On circuit-size complexity and the low hierarchy in NP. SIAM Journal on Computing, 14(1):41\u201351, 1985.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pages 125\u2013129, 1972.","DOI":"10.1109\/SWAT.1972.29"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"M. Ogihara. Polynomial-time membership comparable sets. In Proceedings of the 9th Structure in Complexity Theory Conference, pages 2\u201311. IEEE Computer Society Press, 1994.","DOI":"10.1109\/SCT.1994.315823"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning. A low and a high hierarchy within NP. Journal of Computer and System Sciences, 27:14\u201328, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR16","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"U. Sch\u00f6ning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37:312\u2013323, 1988.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"27_CR17","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U. Sch\u00f6ning","year":"1989","unstructured":"U. Sch\u00f6ning. Probabilistic complexity classes and lowness. Journal of Computer and System Sciences, 39(1):84\u2013100, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Mathematical Systems Theory, 13:55\u201365, 1979.","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"27_CR19","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1137\/S0097539791218640","volume":"23","author":"M. Sheu","year":"1994","unstructured":"M. Sheu and T. Long. The extended low hierarchy is an infinite hierarchy. SIAM Journal on Computing, 23(3):488\u2013509, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61332-3_159.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:17:56Z","timestamp":1742599076000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61332-3_159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540613329","9783540684619"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-61332-3_159","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}