{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T03:02:31Z","timestamp":1725591751872},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1993,6,1]],"date-time":"1993-06-01T00:00:00Z","timestamp":738892800000},"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":[[1993,6]]},"DOI":"10.1007\/bf01202284","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T08:05:42Z","timestamp":1111737942000},"page":"215-233","source":"Crossref","is-referenced-by-count":13,"title":["On the power of deterministic reductions to C=P"],"prefix":"10.1007","volume":"26","author":[{"given":"Frederic","family":"Green","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","first-page":"30","volume-title":"E-Mail and the Unexpected Power of Interaction","author":"L. Babai","year":"1990","unstructured":"L. Babai, E-Mail and the Unexpected Power of Interaction,Proceedings of the 5th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, New York, 1990, pp. 30?44."},{"key":"CR2","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity Theory I","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"J. L. Balc\u00e1zar, J. Diaz, and J. Gabarr\u00f3,Structural Complexity Theory I, EATCS Monographs on Theoretical Computer Science, Vol. II, Springer-Verlag, New York, 1988."},{"key":"CR3","unstructured":"R. Beigel, Bounded Queries to SAT and the Boolean Hierarchy, Johns Hopkins Technical Report 87-8 (1988), to appear inTheoretical Computer Science."},{"key":"CR4","unstructured":"R. Beigel, R. Chang, and M. Ogiwara, A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies, to appear inMathematical Systems Theory."},{"key":"CR5","first-page":"1","volume-title":"PP is Closed Under Intersection","author":"R. Beigel","year":"1991","unstructured":"R. Beigel, N. Reingold, and D. Spielman, PP is Closed Under Intersection,Proceedings of the 23rd Annual Symposium on Theory of Computing, ACM Press, New York, 1991, pp. 1?9."},{"key":"CR6","volume-title":"Lecture Notes in Computer Science, Vol. 380","author":"A. Bertoni","year":"1989","unstructured":"A. Bertoni, D. Brushi, D. Joseph, M. Sitharam, and P. Young, Generalized Boolean Hierarchies and Boolean Hierarchies over RP,Proceedings of the 7th Conference on Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 380, Springer-Verlag, Berlin, 1989."},{"key":"CR7","first-page":"224","volume-title":"On Truth-Table Reducibility to SAT and the Difference Hierarchy Over NP","author":"S. R. Buss","year":"1988","unstructured":"S. R. Buss and L. Hay, On Truth-Table Reducibility to SAT and the Difference Hierarchy Over NP,Proceedings of the 3rd Conference on Structure in Complexity Theory, IEEE Computer Society Press, New York, 1988, pp. 224?233."},{"key":"CR8","first-page":"148","volume-title":"Lecture Notes in Computer Science, Vol. 247","author":"J.-y. Cai","year":"1987","unstructured":"J.-y. 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, Vol. 247, Springer-Verlag, Berlin, 1987, pp. 148?158."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J.-y. Cai","year":"1988","unstructured":"J.-y. Cai, T. Gunderman, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung, The Boolean Hierarchy I: Structural Properties,SIAM Journal of Computing,17 (1988), 1232?1252.","journal-title":"SIAM Journal of Computing"},{"key":"CR10","first-page":"169","volume-title":"The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection","author":"R. Chang","year":"1990","unstructured":"R. Chang and J. Kadin, The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection,Proceedings of the 5th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, New York, 1990, pp. 169?178."},{"key":"CR11","first-page":"140","volume-title":"A Survey on Counting Classes","author":"T. Gundermann","year":"1990","unstructured":"T. Gundermann, N. A. Nasser, and G. Wechsung, A Survey on Counting Classes,Proceedings of the 5th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, New York, 1990, pp. 140?153."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. A. Hemachandra","year":"1989","unstructured":"L. A. Hemachandra, The Strong Exponential Hierarchy Collapses,Journal of Computer and System Science,39 (1989), 299?322.","journal-title":"Journal of Computer and System Science"},{"key":"CR13","unstructured":"J. Kadin, Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy, Ph.D. thesis, Cornell University, February 1988."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautenmann","year":"1983","unstructured":"C. Lautenmann, BPP and the Polynomial Hierarchy,Information Processing Letters,17 (1983), 215?217.","journal-title":"Information Processing Letters"},{"key":"CR15","unstructured":"M. Ogiwara, Generalized Theorems on Relationships Among Reducibility Notions to Certain Complexity Classes, Manuscript, April 1991."},{"key":"CR16","first-page":"238","volume-title":"Lecture Notes in Computer Science, Vol. 480","author":"J. Tarui","year":"1991","unstructured":"J. Tarui, Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy,Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 480, Springer-Verlag, Berlin, 1991, pp. 238?250."},{"key":"CR17","first-page":"382","volume-title":"Degree Complexity of Boolean Functions and Its Applications to Relativized Separations","author":"J. Tarui","year":"1991","unstructured":"J. Tarui, Degree Complexity of Boolean Functions and Its Applications to Relativized Separations,Proceedings of the 6th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, New York, 1991, pp. 382?390."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"S. Toda, On the computational power of PP and ? P,Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 514?519.","DOI":"10.1109\/SFCS.1989.63527"},{"key":"CR19","unstructured":"S. Toda, On Polynomial-Time Truth-Table Reducibility to C = P Sets, Colloquium, Department of Computer Science, University of Chicago, October 26, 1990."},{"key":"CR20","first-page":"2","volume-title":"Counting Classes Are at Least as Hard as the Polynomial-Time Hierarchy","author":"S. Toda","year":"1991","unstructured":"S. Toda and M. Ogiwara, Counting Classes Are at Least as Hard as the Polynomial-Time Hierarchy,Proceedings of the 6th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, New York, 1991, pp. 2?12."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n, Structural Properties of the Counting Hierarchy, Ph.D. thesis, Facultat d'lnformatica de Barcelona, 1988.","DOI":"10.1109\/SCT.1988.5281"},{"key":"CR22","first-page":"213","volume-title":"An Oracle Characterization of the Counting Hierarchy","author":"J. Tor\u00e1n","year":"1988","unstructured":"J. Tor\u00e1n, An Oracle Characterization of the Counting Hierarchy,Proceedings of the 3rd Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, New York, 1988, pp. 213?223."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"K. Wagner, Compact Descriptions and the Counting Polynomial Time Hierarchy,Acta Informatica,23 (1986), 325?356.","journal-title":"Acta Informatica"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"K. Wagner, Bounded Query Classes,SIAM Journal of Computing,19 (1990), 833?846.","journal-title":"SIAM Journal of Computing"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202284.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01202284\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:55:55Z","timestamp":1586181355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01202284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["BF01202284"],"URL":"https:\/\/doi.org\/10.1007\/bf01202284","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}