×

On the power of deterministic reductions to C\(_ =\)P. (English) Zbl 0776.68045

The power of the classes C\(_ =\)P and co-C\(_ =\)P is investigated and compared with the classes co-NP and NP, as well as with PP. The main results of Section 3 say that C\(_ =\)P has similar properties as co-NP, and thus co-C\(_ =\)P behaves similar to NP, e.g., C\(_ =\)P is closed under the for-all operator. Also, C\(_ =\)P is closed under complementation if and only if PH\(^{\text{PP}}\)=C\(_ =\)P.
In Section 5 the author shows that for some oracle \(A\), \(\oplus\text{P}^ A\) is not contained in \(\text{P}^{\text{C}_ =\text{P}^ A}\) and the same for BPP instead of \(\oplus \text{ P}\). This clearly distinguishes C\(_ =\)P from PP, although both classes are defined similarly and share properties like \(\text{NP}^{\text{C}_ = \text{P}}=\text{NP}^{\text{PP}}\).

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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.
[2] J. L. Balcázar, J. Diaz, and J. Gabarró,Structural Complexity Theory I, EATCS Monographs on Theoretical Computer Science, Vol. II, Springer-Verlag, New York, 1988.
[3] R. Beigel, Bounded Queries to SAT and the Boolean Hierarchy, Johns Hopkins Technical Report 87-8 (1988), to appear inTheoretical Computer Science.
[4] R. Beigel, R. Chang, and M. Ogiwara, A Relationship Between Difference Hierarchies and Relativized Polynomial Hierarchies, to appear inMathematical Systems Theory. · Zbl 0776.68043
[5] 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. · Zbl 0827.68040
[6] 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. · Zbl 0756.68037
[7] 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.
[8] 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. · Zbl 0634.68028
[9] 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. · Zbl 0676.68011
[10] 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. · Zbl 0844.68048
[11] 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.
[12] L. A. Hemachandra, The Strong Exponential Hierarchy Collapses,Journal of Computer and System Science,39 (1989), 299-322. · Zbl 0693.03022
[13] J. Kadin, Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy, Ph.D. thesis, Cornell University, February 1988. · Zbl 0664.03031
[14] C. Lautenmann, BPP and the Polynomial Hierarchy,Information Processing Letters,17 (1983), 215-217. · Zbl 0515.68042
[15] M. Ogiwara, Generalized Theorems on Relationships Among Reducibility Notions to Certain Complexity Classes, Manuscript, April 1991. · Zbl 0813.68105
[16] 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. · Zbl 0764.94026
[17] 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.
[18] 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.
[19] S. Toda, On Polynomial-Time Truth-Table Reducibility to C = P Sets, Colloquium, Department of Computer Science, University of Chicago, October 26, 1990.
[20] 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. · Zbl 0755.68055
[21] J. Torán, Structural Properties of the Counting Hierarchy, Ph.D. thesis, Facultat d’lnformatica de Barcelona, 1988.
[22] J. Torán, 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.
[23] K. Wagner, Compact Descriptions and the Counting Polynomial Time Hierarchy,Acta Informatica,23 (1986), 325-356. · Zbl 0621.68032
[24] K. Wagner, Bounded Query Classes,SIAM Journal of Computing,19 (1990), 833-846. · Zbl 0711.68047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.