Immunity and Simplicity for Exact Counting and Other Counting Classes

J. Rothe

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

top
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, C = P , and ⊕P in all possible pairwise combinations. Our main result is that there is an oracle A relative to which C = P contains a set that is immune BPP⊕P. In particular, this 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 C = P -immune set, and ⊕P contains a PPPH-immune set. This implies the existence of a 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.

How to cite

top

Rothe, 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
  1. T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP question. SIAM J. Comput.4 (1975) 431-442.  
  2. J. Balcázar, Simplicity, relativizations and nondeterminism. SIAM J. Comput.14 (1985) 148-157.  
  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.  
  5. R. Beigel, Relativized counting classes: Relations among thresholds, parity, and mods. J. Comput. System Sci.42 (1991) 76-96.  
  6. R. Beigel, Perceptrons, PP, and the polynomial hierarchy. Computational Complexity4 (1994) 339-349.  
  7. R. Beigel, R. Chang and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies. Math. Systems Theory26 (1993) 293-310.  
  8. C. Bennett and J. Gill, Relative to a random oracle A, P A ≠ NP A ≠ coNP A with probability 1. SIAM J. Comput.10 (1981) 96-113.  
  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.  
  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.  
  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.  
  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.  
  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 Theory17 (1984) 13-27.  
  16. J. Gill, Computational complexity of probabilistic Turing machines. SIAM J. Comput.6 (1977) 675-695.  
  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.  
  18. F. Green, An oracle separating ⊕P from PPPH.Inform. Process. Lett. 37 (1991) 149-153.  
  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.  
  22. L. Hemaspaandra and M. Zimand, Strong self-reducibility precludes strong immunity. Math. Systems Theory29 (1996) 535-548.  
  23. S. Homer and W. Maass, Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci.24 (1983) 279-289.  
  24. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979).  
  25. K. Ko, Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput.18 (1989) 392-408.  
  26. K. Ko, A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO, Theoret. Informatics Appl.24 (1990) 229-240.  
  27. R. Ladner, N. Lynch and A. Selman, A comparison of polynomial time reducibilities. Theoret. Comput. Sci.1 (1975) 103-124.  
  28. C. Lautemann, BPP and the polynomial hierarchy. Inform. Process. Lett.17 (1983) 215-217.  
  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.  
  32. N. Nisan and A. Wigderson, Hardness vs randomness. J. Comput. System Sci.49 (1994) 149-167.  
  33. C. Papadimitriou, Computational Complexity. Addison-Wesley (1994).  
  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.  
  36. K. Regan and J. Royer, On closure properties of bounded two-sided error complexity classes. Math. Systems Theory28 (1995) 229-243.  
  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).  
  39. U. Schöning and R. Book, Immunity, relativization, and nondeterminism. SIAM J. Comput.13 (1984) 329-337.  
  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.  
  45. S. Toda, PP is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865-877.  
  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.  
  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.  
  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.  
  51. K. Wagner, The complexity of combinatorial problems with succinct input representations. Acta Inform.23 (1986) 325-356.  
  52. C. Wrathall, Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci.3 (1977) 23-33.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.