Immunity and simplicity for exact counting and other counting classes

Rothe, J.

Rothe, J.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 2, pp. 159-176.

MR Zbl

@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},
     pages = {159--176},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {2},
     year = {1999},
     mrnumber = {1707968},
     zbl = {0946.68051},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1999__33_2_159_0/}
}

TY  - JOUR
AU  - Rothe, J.
TI  - Immunity and simplicity for exact counting and other counting classes
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1999
SP  - 159
EP  - 176
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1999__33_2_159_0/
LA  - en
ID  - ITA_1999__33_2_159_0
ER  -

%0 Journal Article
%A Rothe, J.
%T Immunity and simplicity for exact counting and other counting classes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 159-176
%V 33
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1999__33_2_159_0/
%G en
%F 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) no. 2, pp. 159-176. http://www.numdam.org/item/ITA_1999__33_2_159_0/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

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

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

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

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

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

[33] C. Papadimitriou, Computational Complexity. Addison-Wesley (1994). | MR | Zbl

[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

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

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

[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

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

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

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

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

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

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

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

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

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

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