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.  Zbl0323.68033
  2. J. Balcázar, Simplicity, relativizations and nondeterminism. SIAM J. Comput.14 (1985) 148-157.  Zbl0567.68027
  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
  5. R. Beigel, Relativized counting classes: Relations among thresholds, parity, and mods. J. Comput. System Sci.42 (1991) 76-96.  Zbl0717.68031
  6. R. Beigel, Perceptrons, PP, and the polynomial hierarchy. Computational Complexity4 (1994) 339-349.  Zbl0829.68059
  7. R. Beigel, R. Chang and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies. Math. Systems Theory26 (1993) 293-310.  Zbl0776.68043
  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.  Zbl0454.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.  
  10. D. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci.104 (1992) 263-283.  Zbl0754.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.  Zbl0755.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.  Zbl0732.68039
  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.  Zbl0766.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.  Zbl0851.68029
  15. M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory17 (1984) 13-27.  Zbl0534.94008
  16. J. Gill, Computational complexity of probabilistic Turing machines. SIAM J. Comput.6 (1977) 675-695.  Zbl0366.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.  Zbl0604.68054
  18. F. Green, An oracle separating ⊕P from PPPH.Inform. Process. Lett. 37 (1991) 149-153.  Zbl0714.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.  
  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
  22. L. Hemaspaandra and M. Zimand, Strong self-reducibility precludes strong immunity. Math. Systems Theory29 (1996) 535-548.  Zbl0857.68046
  23. S. Homer and W. Maass, Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci.24 (1983) 279-289.  Zbl0543.03024
  24. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979).  Zbl0426.68001
  25. K. Ko, Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput.18 (1989) 392-408.  Zbl0679.68088
  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
  27. R. Ladner, N. Lynch and A. Selman, A comparison of polynomial time reducibilities. Theoret. Comput. Sci.1 (1975) 103-124.  Zbl0321.68039
  28. C. Lautemann, BPP and the polynomial hierarchy. Inform. Process. Lett.17 (1983) 215-217.  Zbl0515.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.  
  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.  Zbl0771.68053
  32. N. Nisan and A. Wigderson, Hardness vs randomness. J. Comput. System Sci.49 (1994) 149-167.  Zbl0821.68057
  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.  Zbl0632.94030
  36. K. Regan and J. Royer, On closure properties of bounded two-sided error complexity classes. Math. Systems Theory28 (1995) 229-243.  Zbl0827.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.  
  38. J. Rothe, Immunity and simplicity for exact counting and other counting classes. Technical Report TR 679, University of Rochester, Rochester, NY (1998).  Zbl0946.68051
  39. U. Schöning and R. Book, Immunity, relativization, and nondeterminism. SIAM J. Comput.13 (1984) 329-337.  Zbl0558.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.  Zbl0353.02024
  45. S. Toda, PP is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865-877.  Zbl0733.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.  Zbl0755.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.  Zbl0799.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.  Zbl0664.68049
  51. K. Wagner, The complexity of combinatorial problems with succinct input representations. Acta Inform.23 (1986) 325-356.  Zbl0621.68032
  52. C. Wrathall, Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci.3 (1977) 23-33.  Zbl0366.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.  

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.