×

Immunity and simplicity for exact counting and other counting classes. (English) Zbl 0946.68051

Summary: Ker-I Ko [RAIRO, Inf. Théor. Appl. 24, No. 3, 229-240 (1990; Zbl 0701.68032)] and D. Bruschi [Theor. Comput. Sci. 102, No. 2, 215-252 (1992; Zbl 0755.68050)] independently showed that, in some relativized world, PSPACE (in fact, \(\oplus\text{P}\)) contains a set that is immune to the Polynomial Hierarchy (PH). In this paper, we study and settle the question of relativized separations with immunity for PH and the counting classes PP, CP, and \(\oplus\text{P}\) in all possible pairwise combinations. Our main result is that there is an oracle \(A\) relative to which CP contains a set that is immune to \(\text{BPP}^{\oplus\text{P}}\). In particular, this CP\(^A\) set is immune to PH\(^A\) and to \(\oplus\text{P}^A\). Strengthening results of J. Torán [J. Assoc. Comput. Mach. 38, No. 3, 753-774 (1991; Zbl 0799.68080)] and F. Green [Inf. Process. Lett. 37, No. 3, 149-153 (1991; Zbl 0714.68032)], we also show that, in suitable relativizations, NP contains a C=P-immune set, and \(\oplus\text{P}\) and a \(\text{PP}^{\text{PH}}\)-immune set. This implies the existence of a CP\(^B\)-simple set for some oracle \(B\), which extends results of J. L. Balcázar [SIAM J. Comput. 14, 148-157 (1985; Zbl 0567.68027)]and J. L. Balcázar and D. A. Russo, [RAIRO, Inf. Théor. Appl. 22, No. 2, 227-244 (1988; Zbl 0647.68053)]. Our proof technique requires a circuit lower bound for “exact counting” that is derived from A. A. Razborov [Mat. Zametki 41, No. 4, 598-607 (1987; Zbl 0632.94030)] circuit lower bound for majority.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
03D15 Complexity of computation (including implicit computational complexity)

References:

[1] T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP question. SIAM J. Comput.4 (1975) 431-442. · Zbl 0323.68033 · doi:10.1137/0204037
[2] J. Balcázar, Simplicity, relativizations and nondeterminism. SIAM J. Comput.14 (1985) 148-157. · Zbl 0567.68027 · doi:10.1137/0214012
[3] J. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I. EATCS Monographs in theoretical computer science. Springer-Verlag (1988).
[4] J. Balcázar and D. Russo, Immunity and simplicity in relativizations of probabilistic complexity classes. RAIRO, Theoret. Informatics Appl.22 (1988) 227-244. Zbl0647.68053 · Zbl 0647.68053
[5] R. Beigel, Relativized counting classes: Relations among thresholds, parity, and mods. J. Comput. System Sci.42 (1991) 76-96. Zbl0717.68031 · Zbl 0717.68031 · doi:10.1016/0022-0000(91)90040-C
[6] R. Beigel, Perceptrons, PP, and the polynomial hierarchy. Computational Complexity4 (1994) 339-349. · Zbl 0829.68059 · doi:10.1007/BF01263422
[7] R. Beigel, R. Chang and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies. Math. Systems Theory26 (1993) 293-310. · Zbl 0776.68043 · doi:10.1007/BF01371729
[8] C. Bennett and J. Gill, Relative to a random oracle A, P A \neq NP A \neq coNP A with probability 1. SIAM J. Comput.10 (1981) 96-113. · Zbl 0454.68030 · doi:10.1137/0210008
[9] C. Berg and S. Ulfberg, A lower bound for perceptrons and an oracle separation of the PPPH hierarchy. J. Comput. System Sci., to appear. A preliminary version appeared, in Proc. of the 12th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press (1997) 165-172.
[10] D. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci.104 (1992) 263-283. · Zbl 0754.68049 · doi:10.1016/0304-3975(92)90125-Y
[11] D. Bruschi, Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets. Theoret. Comput. Sci.102 (1992) 215-252. · Zbl 0755.68050 · doi:10.1016/0304-3975(92)90232-5
[12] D. Bruschi, D. Joseph and P. Young, Strong separations for the boolean hierarchy over RP. Internat. J. Foundations Comput. Sci.1 (1990) 201-218. · Zbl 0732.68039 · doi:10.1142/S0129054190000151
[13] D. Eppstein, L. Hemachandra, J. Tisdall and B. Yener, Simultaneous strong separations of probabilistic and unambiguous complexity classes. Math. Systems Theory25 (1992) 23-36. · Zbl 0766.68038 · doi:10.1007/BF01368782
[14] L. Fortnow and N. Reingold, PP is closed under truth-table reductions, in Proc. of the 6th Structure in Complexity Theory Conference, IEEE Computer Society Press (1991) 13-15. · Zbl 0851.68029
[15] M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory17 (1984) 13-27. · Zbl 0534.94008 · doi:10.1007/BF01744431
[16] J. Gill, Computational complexity of probabilistic Turing machines. SIAM J. Comput.6 (1977) 675-695. · Zbl 0366.02024 · doi:10.1137/0206049
[17] L. Goldschlager and I. Parberry, On the construction of parallel computers from various bases of boolean functions. Theoret. Comput. Sci.43 (1986) 43-58. Zbl0604.68054 · Zbl 0604.68054 · doi:10.1016/0304-3975(86)90165-9
[18] F. Green, An oracle separating \oplus P from PPPH.Inform. Process. Lett. 37 (1991) 149-153. Zbl0714.68032 · Zbl 0714.68032 · doi:10.1016/0020-0190(91)90035-G
[19] T. Gundermann, N. Nasser and G. Wechsung, A survey on counting classes, in Proc. of the 5th Structure in Complexity Theory Conference, IEEE Computer Society Press (1990) 140-153.
[20] J. Håstad, Almost optimal lower bounds for small depth circuits, in S. Micali, Ed., Randomness and Computation 5 of Advances in Computing Research. JAI Press, Greenwich (1989) 143-170.
[21] L. Hemaspaandra, J. Rothe and G. Wechsung, Easy sets and hard certificate schemes. Acta Inform.34 (1997) 859-879. Zbl0883.68072 · Zbl 0883.68072 · doi:10.1007/s002360050109
[22] L. Hemaspaandra and M. Zimand, Strong self-reducibility precludes strong immunity. Math. Systems Theory29 (1996) 535-548. · Zbl 0857.68046 · doi:10.1007/BF01184814
[23] S. Homer and W. Maass, Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci.24 (1983) 279-289. · Zbl 0543.03024 · doi:10.1016/0304-3975(83)90003-8
[24] J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). Zbl0426.68001 · Zbl 0426.68001
[25] K. Ko, Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput.18 (1989) 392-408. · Zbl 0679.68088 · doi:10.1137/0218027
[26] K. Ko, A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO, Theoret. Informatics Appl.24 (1990) 229-240. Zbl0701.68032 · Zbl 0701.68032
[27] R. Ladner, N. Lynch and A. Selman, A comparison of polynomial time reducibilities. Theoret. Comput. Sci.1 (1975) 103-124. Zbl0321.68039 · Zbl 0321.68039 · doi:10.1016/0304-3975(75)90016-X
[28] C. Lautemann, BPP and the polynomial hierarchy. Inform. Process. Lett.17 (1983) 215-217. · Zbl 0515.68042 · doi:10.1016/0020-0190(83)90044-3
[29] G. Lischke, Towards the actual relationship between NP and exponential time. Mathematical Logic Quarterly, to appear. A preliminary version has appeared as: Impossibilities and possibilities of weak separation between NP and exponential time, in Proc. of the 5th Structure in Complexity Theory Conference, IEEE Computer Society Press (1990) 245-253.
[30] A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space, in Proc. of the 13th IEEE Symposium on Switching and Automata Theory (1972) 125-129.
[31] H. Müller, A note on balanced immunity. Math. Systems Theory26 (1993) 157-167. · Zbl 0771.68053 · doi:10.1007/BF01202280
[32] N. Nisan and A. Wigderson, Hardness vs randomness. J. Comput. System Sci.49 (1994) 149-167. · Zbl 0821.68057 · doi:10.1016/S0022-0000(05)80043-1
[33] C. Papadimitriou, Computational Complexity. Addison-Wesley (1994). Zbl0833.68049 · Zbl 0833.68049
[34] C. Papadimitriou and S. Zachos, Two remarks on the power of counting, in Proc. of the 6th GI Conference on Theoretical Computer Science, Springer-Verlag, Lecture Notes in Computer Science145 (1983) 269-276.
[35] A. Razborov, Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mat. Zametki41 (1987) 598-607. In Russian. English Translation in Mathematical Notes of the Academy of Sciences of the USSR41 (1987) 333-338. · Zbl 0632.94030 · doi:10.1007/BF01137685
[36] K. Regan and J. Royer, On closure properties of bounded two-sided error complexity classes. Math. Systems Theory28 (1995) 229-243. Zbl0827.68046 · Zbl 0827.68046 · doi:10.1007/BF01303057
[37] J. Rothe, Some closure properties of GAP-definable classes. Technical Report TR Math/93/6, Friedrich-Schiller-Universität Jena, Jena, Germany (1993). Appeared as part of: A promise class at least as hard as the polynomial hierarchy. J. Comput. Inform.1 (1995) 92-107.
[38] J. Rothe, Immunity and simplicity for exact counting and other counting classes. Technical Report TR 679, University of Rochester, Rochester, NY (1998). · Zbl 0946.68051
[39] U. Schöning and R. Book, Immunity, relativization, and nondeterminism. SIAM J. Comput.13 (1984) 329-337. · Zbl 0558.68039 · doi:10.1137/0213023
[40] J. Simon, On Some Central Problems in Computational Complexity. PhD thesis, Cornell University, Ithaca, NY (1975). Available as Cornell Department of Computer Science Technical Report TR75-224.
[41] M. Sipser, Borel sets and circuit complexity, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 61-69.
[42] M. Sipser, A complexity theoretic approach to randomness, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 330-335.
[43] R. Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity, in Proc. of the 19th ACM Symposium on Theory of Computing, ACM Press (1987) 77-82.
[44] L. Stockmeyer, The polynomial-time hierarchy. Theoret. Comput. Sci.3 (1977) 1-22. · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
[45] S. Toda, PP is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865-877. · Zbl 0733.68034 · doi:10.1137/0220053
[46] S. Toda and M. Ogiwara, Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput.21 (1992) 316-328. · Zbl 0755.68055 · doi:10.1137/0221023
[47] J. Torán, Structural Properties of the Counting Hierarchies. PhD thesis, Universitat Politècnica de Catalunya, Barcelona (1988).
[48] J. Torán, Complexity classes defined by counting quantifiers. J. Assoc. Comput. Mach.38 (1991) 753-774. Zbl0799.68080 · Zbl 0799.68080 · doi:10.1145/116825.116858
[49] L. Torenvliet, Structural Concepts in Relativised Hierarchies. PhD thesis, Universiteit van Amsterdam, Amsterdam, The Netherlands (1986).
[50] L. Torenvliet and P. van Emde Boas, Simplicity, immunity, relativizations and nondeterminism. Inform. and Comput.80 (1989) 1-17. Zbl0664.68049 · Zbl 0664.68049 · doi:10.1016/0890-5401(89)90020-5
[51] K. Wagner, The complexity of combinatorial problems with succinct input representations. Acta Inform.23 (1986) 325-356. Zbl0621.68032 · Zbl 0621.68032 · doi:10.1007/BF00289117
[52] C. Wrathall, Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci.3 (1977) 23-33. Zbl0366.02031 · Zbl 0366.02031 · doi:10.1016/0304-3975(76)90062-1
[53] A. Yao, Separating the polynomial-time hierarchy by oracles, in Proc. of the 26th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press (1985) 1-10.
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.