{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:27Z","timestamp":1725456747807},"publisher-location":"Berlin\/Heidelberg","reference-count":44,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029617","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:33:46Z","timestamp":1133397226000},"page":"261-268","source":"Crossref","is-referenced-by-count":1,"title":["On checking versus evaluation of multiple queries"],"prefix":"10.1007","author":[{"given":"William I.","family":"Gasarch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lane A.","family":"Hemachandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Albrecht","family":"Hoene","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","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. Gasarch. Polynomial terse sets. Information and Computation, 77:37\u201356, 1988.","journal-title":"Information and Computation"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender and L. Hemachandra. Lower bounds for the low hierarchy. In Automata, Languages, and Programming (ICALP 1989), pages 31\u201345. Springer-Verlag Lecture Notes in Computer Science #372, July 1989.","DOI":"10.1007\/BFb0035750"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"E. Allender. The complexity of sparse sets in P. In Proceedings 1st Structure in Complexity Theory Conference, pages 1\u201311, Springer-Verlag Lecture Notes in Computer Science #223, June 1986.","DOI":"10.1007\/3-540-16486-3_85"},{"issue":"6","key":"26_CR4","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1137\/0217075","volume":"17","author":"E. Allender","year":"1988","unstructured":"E. Allender and R. Rubinstein. P-printable sets. SIAM Journal on Computing, 17(6):1193\u20131202, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR5","first-page":"1251","volume":"9","author":"Y. Barzdin'","year":"1968","unstructured":"Y. Barzdin'. Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set. Soviet Math. Dokl., 9:1251\u20131254, 1968.","journal-title":"Soviet Math. Dokl."},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"[BBJ+] A. Bertoni, D. Bruschi, D. Joseph, M. Sitharam, and P. Young. Generalized boolean hierarchies and boolean hierarchies over RP. Manuscript, 1989. Preliminary version appears in Proceedings Fundamentals of Computation Theory, Springer-Verlag Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-51498-8_4"},{"key":"26_CR7","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:739\u2013747, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR8","unstructured":"R. Beigel. A structural theorem that depends quantitatively on the complexity of SAT. In Proceedings of the 2nd Annual Conference on Structure in Complexity Theory, pages 28\u201332. IEEE Computer Society Press, June 1987."},{"key":"26_CR9","unstructured":"R. Beigel. Bounded queries to SAT and the Boolean hierarchy. Unpublished manuscript, August 1988."},{"key":"26_CR10","unstructured":"R. Beigel. NP-hard sets are P-superterse unless R=NP. Technical Report 88-04, Johns Hopkins Department of Computer Science, August 1988."},{"key":"26_CR11","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich. On the unique satisfiability problem. Information and Control, 55:80\u201388, 1982.","journal-title":"Information and Control"},{"key":"26_CR12","series-title":"Technical Report","volume-title":"Terse, superterse, and verbose sets","author":"R. Beigel","year":"1987","unstructured":"R. Beigel, W. Gasarch, J. Gill, and J. Owings. Terse, superterse, and verbose sets. Technical Report TR-1806, University of Maryland, Department of Computer Science, College Park, Maryland, 1987."},{"issue":"4","key":"26_CR13","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question. SIAM Journal on Computing, 4(4):431\u2013442, 1975.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"26_CR14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0022-0000(89)90033-0","volume":"38","author":"J. Cai","year":"1989","unstructured":"J. Cai. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. Journal of Computer and System Sciences, 38(1):68\u201385, 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"26_CR15","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"[CGH+88] J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232\u20131252, December 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"26_CR16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"[CGH+89] J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95\u2013111, February 1989.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR17","unstructured":"J. Cai and L. Hemachandra. On the power of parity polynomial time. Mathematical Systems Theory. To appear."},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"R. Chang. On the structure of bounded queries to arbitrary NP sets. In Proceedings of the 4th Conference on Structure in Complexity Theory, pages 250\u2013258. IEEE Computer Science Press, June 1989.","DOI":"10.1109\/SCT.1989.41832"},{"key":"26_CR19","series-title":"Technical Report","volume-title":"The boolean hierarchy and the polynomial hierarchy: A closer connection","author":"R. Chang","year":"1989","unstructured":"R. Chang and J. Kadin. The boolean hierarchy and the polynomial hierarchy: A closer connection. Technical Report TR 89-1008, Department of Computer Science, Cornell University, Ithaca, NY, May 1989."},{"key":"26_CR20","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BFb0090937","volume-title":"Logic Year 1979\u201380, The University of Connecticut","author":"R. Epstein","year":"1981","unstructured":"R. Epstein, R. Haas, and R. Kramer. Hierarchies of sets and degrees below 0'. In Logic Year 1979\u201380, The University of Connecticut, Lecture Notes in Mathematics #859, pages 32\u201347. Springer-Verlag, Berlin, 1981."},{"issue":"4","key":"26_CR21","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675\u2013695, December 1977.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR22","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"L. Goldschlager","year":"1986","unstructured":"L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of Boolean functions. Theoretical computer Science, 43:43\u201358, 1986.","journal-title":"Theoretical computer Science"},{"issue":"5","key":"26_CR23","first-page":"395","volume":"6","author":"T. Gundermann","year":"1987","unstructured":"T. Gundermann and G. Wechsung. Counting classes with finite acceptance types. Computers and Artificial Types, 6(5):395\u2013409, 1987.","journal-title":"Computers and Artificial Types"},{"key":"26_CR24","unstructured":"F. Hausdorff. Grundz\u00fcge der Mengenlehre. Leipzig, 1914."},{"issue":"3","key":"26_CR25","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\u2013322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR26","series-title":"Technical Report","volume-title":"On checking versus evaluation of multiple queries: Characteristic vector terseness","author":"L. Hemachandra","year":"1988","unstructured":"L. Hemachandra and A. Hoene. On checking versus evaluation of multiple queries: Characteristic vector terseness. Technical Report No. 88-21, Technische Universit\u00e4t, Berlin, October 1988."},{"issue":"2\/3","key":"26_CR27","first-page":"159","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis, N. Immerman, and V. Sewelson. Sparse sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, 65(2\/3):159\u2013181, May\/June 1985.","journal-title":"Information and Control"},{"key":"26_CR28","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"issue":"2","key":"26_CR29","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1090\/S0002-9947-1968-0220595-7","volume":"131","author":"C. Jockusch","year":"1968","unstructured":"C. Jockusch. Semirecursive sets and positive reducibility. Transactions of the AMS, 131(2):420\u2013436, 1968.","journal-title":"Transactions of the AMS"},{"key":"26_CR30","unstructured":"C. Jockusch. Recursion theory: Its generalizations and applications. In Proceedings of the Logic Colloquium, Leeds, pages 140\u2013157. Cambridge University Press, 1979."},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"[K88] J. K\u00e4mper. Non-uniform proof systems: a new framework to describe non-uniform and probabilistic complexity classes. In 8th Conference on Foundations of Software Technology and Theoretical Computer Science (FST-TCS 1988), pages 193\u2013210. Springer-Verlag Lecture Notes in Computer Science #338, December 1988.","DOI":"10.1007\/3-540-50517-2_81"},{"issue":"6","key":"26_CR32","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\u20131282, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"26_CR33","doi-asserted-by":"crossref","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":"26_CR34","first-page":"419","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and K. Wagner. The difference and truth-table hierarchies for NP. R.A.I.R.O. Informatique th\u00e9orique et Applications, 21:419\u2013435, 1987.","journal-title":"R.A.I.R.O. Informatique th\u00e9orique et Applications"},{"key":"26_CR35","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:244\u2013259, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR36","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings 6th GI Conference on Theoretical Computer Science, pages 269\u2013276. Springer-Verlag Lecture Notes in Computer Science #145, 1983.","DOI":"10.1007\/BFb0009651"},{"key":"26_CR37","unstructured":"H. Rogers, Jr. The Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967."},{"key":"26_CR38","volume-title":"Structural Complexity Classes of Sparse Sets: Intractability, Data Compression and Printability","author":"R. Rubinstein","year":"1988","unstructured":"R. Rubinstein. Structural Complexity Classes of Sparse Sets: Intractability, Data Compression and Printability. PhD thesis, Northeastern University, Boston, MA, August 1988."},{"key":"26_CR39","doi-asserted-by":"crossref","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 in NP. Journal of Computer and System Sciences., 27:14\u201328, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR40","doi-asserted-by":"crossref","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"},{"key":"26_CR41","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. The relative complexity of checking and evaluting. Information Processing Letters, 5:20\u201323, 1976.","journal-title":"Information Processing Letters"},{"key":"26_CR42","volume-title":"Bounded query classes","author":"K. Wagner","year":"1987","unstructured":"K. Wagner. Bounded query classes. Institut f\u00fcr Mathematik 157, Augsburg, Augsburg, W. Germany, October 1987."},{"key":"26_CR43","doi-asserted-by":"crossref","unstructured":"K. Wagner. Bounded query computation. In Proceedings 3rd Structure in Complexity Theory Conference, pages 260\u2013277. IEEE Computer Society Press, June 1988.","DOI":"10.1109\/SCT.1988.5286"},{"key":"26_CR44","doi-asserted-by":"crossref","unstructured":"G. Wechsung. On the boolean closure of NP. In Proceedings of the International Conference on Fundamentals of Computation Theory, pages 485\u2013493. Springer-Verlag, Lecture Notes in Computer Science, 1985.","DOI":"10.1007\/BFb0028832"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029617","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T04:15:34Z","timestamp":1586578534000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029617"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/bfb0029617","relation":{},"subject":[]}}