{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T23:10:19Z","timestamp":1735427419150,"version":"3.32.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,5,1]],"date-time":"1995-05-01T00:00:00Z","timestamp":799286400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1995,5]]},"DOI":"10.1007\/bf01303054","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T17:50:37Z","timestamp":1111773037000},"page":"173-198","source":"Crossref","is-referenced-by-count":25,"title":["On computing Boolean connectives of characteristic functions"],"prefix":"10.1007","volume":"28","author":[{"given":"R.","family":"Chang","sequence":"first","affiliation":[]},{"given":"J.","family":"Kadin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"A. Amir, R. Beigel, and W. I. Gasarch. Some connections between bounded query classes and non-uniform complexity.Proceedings of the 5th Structure in Complexity Theory Conference, pages 232?243, 1990.","DOI":"10.1109\/SCT.1990.113971"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0890-5401(88)90044-2","volume":"77","author":"A. Amir","year":"1988","unstructured":"A. Amir and W. I. Gasarch. Polynomial terse sets.Information and Computation,77:37?56, April 1988.","journal-title":"Information and Computation"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"A. Bertoni, D. Bruschi, D. Joseph, M. Sitharam, and P. Young. Generalized Boolean hierarchies and the hierarchy over RP. Technical Report 809, Department of Computer Sciences, University of Wisconsin-Madison, 1989.","DOI":"10.1007\/3-540-51498-8_4"},{"key":"CR4","unstructured":"R. Beigel. NP-hard sets are p-supertese unless R = NP. Technical Report 4, Department of Computer Science, The Johns Hopkins University, 1988."},{"issue":"2","key":"CR5","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0304-3975(91)90160-4","volume":"84","author":"R. Beigel","year":"1991","unstructured":"R. Beigel. Bounded queries to SAT and the Boolean hierarchy.Theoretical Computer Science,84(2):199?223, July 1991.","journal-title":"Theoretical Computer Science"},{"key":"CR6","first-page":"148","volume-title":"Lecture Notes in Computer Science","author":"J. Cai","year":"1987","unstructured":"J. Cai. Probability one separation of the Boolean hierarchy.Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, pages 148?158, volume 247. Springer-Verlag, Berlin, 1987."},{"issue":"6","key":"CR7","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V Sewelson, K. Wagner, and G. Wechsung. The Boolean hierarchy, I: Structural properties.SLAM Journal on Computing,17(6):1232?1252, December 1988.","journal-title":"SLAM Journal on Computing"},{"key":"CR8","unstructured":"J. Cai and L. A. Hemachandra. The Boolean hierarchy: Hardware over NP. Technical Report TR 85-724, Department of Computer Science, Cornell University, December 1985."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"R. Chang. On the structure of bounded queries to arbitrary NP sets.Proceedings of the 4th Structure in Complexity Theory Conference, pages 250?258, June 1989. Revised paper inSIAM Journal on Computing,21(4):743?754, August 1992.","DOI":"10.1137\/0221045"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"R. Chang and J. Kadin. The Boolean hierarchy and the polynomial hierarchy: a closer connection.Proceedings of the 5th Structure in Complexity Theory Conference, pages 169?178, July 1990. To appear inSIAM Journal on Computing.","DOI":"10.1109\/SCT.1990.113965"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"R. Chang, J. Kadin, and P. Rohatgi. Connections between the complexity of unique satisfiability and the threshold behavior of randomized reductions.Proceedings of the 6th Structure in Complexity Theory Conference, pages 255?269, July 1991. Revised paper to appear inJournal of Computer and System Sciences.","DOI":"10.1109\/SCT.1991.160268"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"J. Goldsmith, D. Joseph, and P. Young. Self-reducible, p-selective, near-testable, and p-cheatable sets: The effect of internal structure on the complexity of a set.Proceedings of the 2nd Structure in Complexity Theory Conference, pages 50?59, 1987.","DOI":"10.1109\/PSCT.1987.10319254"},{"issue":"3","key":"CR13","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses.Journal of Computer and System Sciences,39(3):299?322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR14","volume-title":"Lecture Notes in Computer Science, volume 136","author":"C. M. Hoffman","year":"1979","unstructured":"C. M. Hoffman,Group-Theoretic Algorithms and Graph Isomorphism. Lecture Notes in Computer Science, volume 136. Springer-Verlag, Berlin, 1979."},{"issue":"6","key":"CR15","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses.SIAM Journal on Computing,17(6):1263?1282, December 1988.","journal-title":"SIAM Journal on Computing"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","volume":"39","author":"J. Kadin","year":"1989","unstructured":"J. Kadin, pNP[log n] and sparse Turing complete sets for NP.Journal of Computer and System Sciences,39:282?298, December 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"CR17","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 System Sciences,36(3):490?509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00f6bler, Uwe Sch\u00f6ning, and K. Wagner. The difference and truth-table hierarchies for NP.RAIRO Theoretical Informatics and Applications,21:419?435, 1987.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"issue":"2","key":"CR19","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities.Theoretical Computer Science,1(2):103?123, 1975.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"CR20","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity).Journal of Computer and System Sciences,28(2):244?259, April 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR21","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?323, December 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. L. Selman","year":"1979","unstructured":"A. L. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP.Mathematical Systems Theory,13:55?65, 1979.","journal-title":"Mathematical Systems Theory"},{"key":"CR23","first-page":"485","volume-title":"Lecture Notes in Computer Science","author":"K. Wagner","year":"1985","unstructured":"K. Wagner and G. Wechsung. On the Boolean closure of NP.Proceedings of the 1985 International Conference on Fundamentals of Computation Theory, Lecture Notes in Computer Science, pages 485?493, volume 199. Springer-Verlag, Berlin, 1985."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01303054.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01303054\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01303054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T22:47:17Z","timestamp":1735426037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01303054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,5]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,5]]}},"alternative-id":["BF01303054"],"URL":"https:\/\/doi.org\/10.1007\/bf01303054","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"type":"print","value":"0025-5661"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[1995,5]]}}}