# Immunity and Simplicity for Exact Counting and Other Counting Classes

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 2, page 159-176
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topRothe, J.. "Immunity and Simplicity for Exact Counting and Other Counting Classes." RAIRO - Theoretical Informatics and Applications 33.2 (2010): 159-176. <http://eudml.org/doc/221974>.

@article{Rothe2010,

abstract = {
Ko [26] and Bruschi [11] independently showed that, in
some relativized world, PSPACE (in fact, ⊕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, $\{\rm C\!\!\!\!=\!\!\!P\}$, and ⊕P
in all possible pairwise combinations. Our main result is that there
is an oracle A relative to which $\{\rm C\!\!\!\!=\!\!\!P\}$ contains a set that is immune BPP⊕P.
In particular, this $\{\rm C\!\!\!\!=\!\!\!P\}^A$ set is immune to PHA and to ⊕PA. Strengthening results of
Torán [48] and Green [18], we also show that, in suitable relativizations,
NP contains a $\{\rm C\!\!\!\!=\!\!\!P\}$-immune set, and ⊕P contains a PPPH-immune
set. This implies the existence of a $\{\rm C\!\!\!\!=\!\!\!P\}^B$-simple set for some
oracle B, which extends results of Balcázar et al. [2,4].
Our proof technique requires a circuit lower bound for “exact
counting” that is derived from Razborov's [35] circuit
lower bound for majority.
},

author = {Rothe, J.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Computational complexity; immunity; counting classes;
relativized computation; circuit lower bounds.; polynomial hierarchy},

language = {eng},

month = {3},

number = {2},

pages = {159-176},

publisher = {EDP Sciences},

title = {Immunity and Simplicity for Exact Counting and Other Counting Classes},

url = {http://eudml.org/doc/221974},

volume = {33},

year = {2010},

}

TY - JOUR

AU - Rothe, J.

TI - Immunity and Simplicity for Exact Counting and Other Counting Classes

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 2

SP - 159

EP - 176

AB -
Ko [26] and Bruschi [11] independently showed that, in
some relativized world, PSPACE (in fact, ⊕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, ${\rm C\!\!\!\!=\!\!\!P}$, and ⊕P
in all possible pairwise combinations. Our main result is that there
is an oracle A relative to which ${\rm C\!\!\!\!=\!\!\!P}$ contains a set that is immune BPP⊕P.
In particular, this ${\rm C\!\!\!\!=\!\!\!P}^A$ set is immune to PHA and to ⊕PA. Strengthening results of
Torán [48] and Green [18], we also show that, in suitable relativizations,
NP contains a ${\rm C\!\!\!\!=\!\!\!P}$-immune set, and ⊕P contains a PPPH-immune
set. This implies the existence of a ${\rm C\!\!\!\!=\!\!\!P}^B$-simple set for some
oracle B, which extends results of Balcázar et al. [2,4].
Our proof technique requires a circuit lower bound for “exact
counting” that is derived from Razborov's [35] circuit
lower bound for majority.

LA - eng

KW - Computational complexity; immunity; counting classes;
relativized computation; circuit lower bounds.; polynomial hierarchy

UR - http://eudml.org/doc/221974

ER -

## References

top- T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP question. SIAM J. Comput.4 (1975) 431-442. Zbl0323.68033
- J. Balcázar, Simplicity, relativizations and nondeterminism. SIAM J. Comput.14 (1985) 148-157. Zbl0567.68027
- J. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I. EATCS Monographs in theoretical computer science. Springer-Verlag (1988).
- 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
- R. Beigel, Relativized counting classes: Relations among thresholds, parity, and mods. J. Comput. System Sci.42 (1991) 76-96. Zbl0717.68031
- R. Beigel, Perceptrons, PP, and the polynomial hierarchy. Computational Complexity4 (1994) 339-349. Zbl0829.68059
- R. Beigel, R. Chang and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies. Math. Systems Theory26 (1993) 293-310. Zbl0776.68043
- C. Bennett and J. Gill, Relative to a random oracle A, ${\mathrm{P}}^{A}\ne {\mathrm{NP}}^{A}\ne {\mathrm{coNP}}^{A}$ with probability 1. SIAM J. Comput.10 (1981) 96-113. Zbl0454.68030
- 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.
- D. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci.104 (1992) 263-283. Zbl0754.68049
- D. Bruschi, Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets. Theoret. Comput. Sci.102 (1992) 215-252. Zbl0755.68050
- D. Bruschi, D. Joseph and P. Young, Strong separations for the boolean hierarchy over RP. Internat. J. Foundations Comput. Sci.1 (1990) 201-218. Zbl0732.68039
- D. Eppstein, L. Hemachandra, J. Tisdall and B. Yener, Simultaneous strong separations of probabilistic and unambiguous complexity classes. Math. Systems Theory25 (1992) 23-36. Zbl0766.68038
- 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. Zbl0851.68029
- M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory17 (1984) 13-27. Zbl0534.94008
- J. Gill, Computational complexity of probabilistic Turing machines. SIAM J. Comput.6 (1977) 675-695. Zbl0366.02024
- 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
- F. Green, An oracle separating ⊕P from PPPH.Inform. Process. Lett. 37 (1991) 149-153. Zbl0714.68032
- 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.
- 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.
- L. Hemaspaandra, J. Rothe and G. Wechsung, Easy sets and hard certificate schemes. Acta Inform.34 (1997) 859-879. Zbl0883.68072
- L. Hemaspaandra and M. Zimand, Strong self-reducibility precludes strong immunity. Math. Systems Theory29 (1996) 535-548. Zbl0857.68046
- S. Homer and W. Maass, Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci.24 (1983) 279-289. Zbl0543.03024
- J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). Zbl0426.68001
- K. Ko, Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput.18 (1989) 392-408. Zbl0679.68088
- K. Ko, A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO, Theoret. Informatics Appl.24 (1990) 229-240. Zbl0701.68032
- R. Ladner, N. Lynch and A. Selman, A comparison of polynomial time reducibilities. Theoret. Comput. Sci.1 (1975) 103-124. Zbl0321.68039
- C. Lautemann, BPP and the polynomial hierarchy. Inform. Process. Lett.17 (1983) 215-217. Zbl0515.68042
- 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.
- 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.
- H. Müller, A note on balanced immunity. Math. Systems Theory26 (1993) 157-167. Zbl0771.68053
- N. Nisan and A. Wigderson, Hardness vs randomness. J. Comput. System Sci.49 (1994) 149-167. Zbl0821.68057
- C. Papadimitriou, Computational Complexity. Addison-Wesley (1994).
- 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.
- 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. Zbl0632.94030
- K. Regan and J. Royer, On closure properties of bounded two-sided error complexity classes. Math. Systems Theory28 (1995) 229-243. Zbl0827.68046
- 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.
- J. Rothe, Immunity and simplicity for exact counting and other counting classes. Technical Report TR 679, University of Rochester, Rochester, NY (1998). Zbl0946.68051
- U. Schöning and R. Book, Immunity, relativization, and nondeterminism. SIAM J. Comput.13 (1984) 329-337. Zbl0558.68039
- 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.
- M. Sipser, Borel sets and circuit complexity, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 61-69.
- M. Sipser, A complexity theoretic approach to randomness, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 330-335.
- 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.
- L. Stockmeyer, The polynomial-time hierarchy. Theoret. Comput. Sci.3 (1977) 1-22. Zbl0353.02024
- S. Toda, PP is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865-877. Zbl0733.68034
- S. Toda and M. Ogiwara, Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput.21 (1992) 316-328. Zbl0755.68055
- J. Torán, Structural Properties of the Counting Hierarchies. PhD thesis, Universitat Politècnica de Catalunya, Barcelona (1988).
- J. Torán, Complexity classes defined by counting quantifiers. J. Assoc. Comput. Mach.38 (1991) 753-774. Zbl0799.68080
- L. Torenvliet, Structural Concepts in Relativised Hierarchies. PhD thesis, Universiteit van Amsterdam, Amsterdam, The Netherlands (1986).
- L. Torenvliet and P. van Emde Boas, Simplicity, immunity, relativizations and nondeterminism. Inform. and Comput.80 (1989) 1-17. Zbl0664.68049
- K. Wagner, The complexity of combinatorial problems with succinct input representations. Acta Inform.23 (1986) 325-356. Zbl0621.68032
- C. Wrathall, Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci.3 (1977) 23-33. Zbl0366.02031
- 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.