Immunity and simplicity for exact counting and other counting classes
Rothe, J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 159-176 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{ITA_1999__33_2_159_0,
     author = {Rothe, J.},
     title = {Immunity and simplicity for exact counting and other counting classes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {159-176},
     mrnumber = {1707968},
     zbl = {0946.68051},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_2_159_0}
}

Rothe, J. Immunity and simplicity for exact counting and other counting classes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 159-176. http://gdmltest.u-ga.fr/item/ITA_1999__33_2_159_0/

[1] T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP question. SIAM J. Comput. 4 (1975) 431-442. | MR 395311 | Zbl 0323.68033

[2] J. Balcázar, Simplicity, relativizations and nondeterminism. SIAM J. Comput. 14 (1985) 148-157. | MR 774935 | Zbl 0567.68027

[3] J. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I. EATCS Monographs in theoretical computer science. Springer-Verlag (1988). | MR 1047862 | Zbl 0638.68040

[4] J. Balcázar and D. Russo, Immunity and simplicity in relativizations of probabilistic complexity classes. RAIRO, Theoret. Informatics Appl. 22 (1988) 227-244. | Numdam | MR 951339 | Zbl 0647.68053

[5] R. Beigel, Relativized counting classes: Relations among thresholds, parity, and mods. J. Comput. System Sci. 42 (1991) 76-96. | MR 1093301 | Zbl 0717.68031

[6] R. Beigel, Perceptrons, PP, and the polynomial hierarchy. Computational Complexity 4 (1994) 339-349. | MR 1313534 | Zbl 0829.68059

[7] R. Beigel, R. Chang and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies. Math. Systems Theory 26 (1993) 293-310. | MR 1209999 | Zbl 0776.68043

[8] C. Bennett and J. Gill, Relative to a random oracle A, PA ≠ NPA ≠ coNPA with probability 1. SIAM J. Comput. 10 (1981) 96-113. | MR 605606 | Zbl 0454.68030

[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. | MR 1758134

[10] D. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. | MR 1186181 | Zbl 0754.68049

[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. | MR 1174734 | Zbl 0755.68050

[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. | MR 1097013 | Zbl 0732.68039

[13] D. Eppstein, L. Hemachandra, J. Tisdall and B. Yener, Simultaneous strong separations of probabilistic and unambiguous complexity classes. Math. Systems Theory 25 (1992) 23-36. | MR 1139093 | Zbl 0766.68038

[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.

[15] M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory 17 (1984) 13-27. | MR 738749 | Zbl 0534.94008

[16] J. Gill, Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977) 675-695. | MR 464691 | Zbl 0366.02024

[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. | MR 847902 | Zbl 0604.68054

[18] F. Green, An oracle separating ⊕P from PPPH. Inform. Process. Lett. 37 (1991) 149-153. | MR 1095698 | Zbl 0714.68032

[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. | MR 1097665

[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. | MR 1480239 | Zbl 0883.68072

[22] L. Hemaspaandra and M. Zimand, Strong self-reducibility precludes strong immunity. Math. Systems Theory 29 (1996) 535-548. | MR 1397918 | Zbl 0857.68046

[23] S. Homer and W. Maass, Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci. 24 (1983) 279-289. | MR 716824 | Zbl 0543.03024

[24] J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). | MR 645539 | Zbl 0426.68001

[25] K. Ko, Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput. 18 (1989) 392-408. | MR 986675 | Zbl 0679.68088

[26] K. Ko, A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO, Theoret. Informatics Appl. 24 (1990) 229-240. | Numdam | MR 1072992 | Zbl 0701.68032

[27] R. Ladner, N. Lynch and A. Selman, A comparison of polynomial time reducibilities. Theoret. Comput. Sci. 1 (1975) 103-124. | MR 395319 | Zbl 0321.68039

[28] C. Lautemann, BPP and the polynomial hierarchy. Inform. Process. Lett. 17 (1983) 215-217. | MR 742072 | Zbl 0515.68042

[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. | MR 1097674 | Zbl 0933.03046

[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 Theory 26 (1993) 157-167. | MR 1196155 | Zbl 0771.68053

[32] N. Nisan and A. Wigderson, Hardness vs randomness. J. Comput. System Sci. 49 (1994) 149-167. | MR 1293639 | Zbl 0821.68057

[33] C. Papadimitriou, Computational Complexity. Addison-Wesley (1994). | MR 1251285 | 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 Science 145 (1983) 269-276. | Zbl 0506.68039

[35] A. Razborov, Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mat. Zametki 41 (1987) 598-607. In Russian. English Translation in Mathematical Notes of the Academy of Sciences of the USSR 41 (1987) 333-338. | MR 897705 | Zbl 0632.94030

[36] K. Regan and J. Royer, On closure properties of bounded two-sided error complexity classes. Math. Systems Theory 28 (1995) 229-243. | MR 1316600 | Zbl 0827.68046

[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. | MR 1647454

[38] J. Rothe, Immunity and simplicity for exact counting and other counting classes. Technical Report TR 679, University of Rochester, Rochester, NY (1998). | MR 1707968

[39] U. Schöning and R. Book, Immunity, relativization, and nondeterminism. SIAM J. Comput. 13 (1984) 329-337. | Zbl 0558.68039

[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. | MR 438810 | Zbl 0353.02024

[45] S. Toda, PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20 (1991) 865-877. | MR 1115655 | Zbl 0733.68034

[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. | MR 1154526 | Zbl 0755.68055

[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. | MR 1125929 | Zbl 0799.68080

[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. | MR 978058 | Zbl 0664.68049

[51] K. Wagner, The complexity of combinatorial problems with succinct input representations. Acta Inform. 23 (1986) 325-356. | MR 853581 | Zbl 0621.68032

[52] C. Wrathall, Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977) 23-33. | MR 438811 | Zbl 0366.02031

[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.