@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://archive.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://archive.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://archive.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, Volume 33 (1999) no. 2, pp. 159-176. http://archive.numdam.org/item/ITA_1999__33_2_159_0/
[1] Relativizations of the P=?NP question. SIAM J. Comput. 4 (1975) 431-442. | MR | Zbl
, and ,[2] Simplicity, relativizations and nondeterminism. SIAM J. Comput. 14 (1985) 148-157. | MR | Zbl
,[3] Structural Complexity I. EATCS Monographs in theoretical computer science. Springer-Verlag (1988). | MR | Zbl
, and ,[4] Immunity and simplicity in relativizations of probabilistic complexity classes. RAIRO, Theoret. Informatics Appl. 22 (1988) 227-244. | Numdam | MR | Zbl
and ,[5] Relativized counting classes: Relations among thresholds, parity, and mods. J. Comput. System Sci. 42 (1991) 76-96. | MR | Zbl
,[6] Perceptrons, PP, and the polynomial hierarchy. Computational Complexity 4 (1994) 339-349. | MR | Zbl
,[7] A relationship between difference hierarchies and relativized polynomial hierarchies. Math. Systems Theory 26 (1993) 293-310. | MR | Zbl
, and ,[8] Relative to a random oracle A, PA ≠ NPA ≠ coNPA with probability 1. SIAM J. Comput. 10 (1981) 96-113. | MR | Zbl
and ,[9] 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
and ,[10] A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. | MR | Zbl
, and ,[11] 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] Strong separations for the boolean hierarchy over RP. Internat. J. Foundations Comput. Sci. 1 (1990) 201-218. | MR | Zbl
, and ,[13] Simultaneous strong separations of probabilistic and unambiguous complexity classes. Math. Systems Theory 25 (1992) 23-36. | MR | Zbl
, , and ,[14] PP is closed under truth-table reductions, in Proc. of the 6th Structure in Complexity Theory Conference, IEEE Computer Society Press (1991) 13-15.
and ,[15] Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory 17 (1984) 13-27. | MR | Zbl
, and ,[16] Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977) 675-695. | MR | Zbl
,[17] On the construction of parallel computers from various bases of boolean functions. Theoret. Comput. Sci. 43 (1986) 43-58. | MR | Zbl
and ,[18] An oracle separating ⊕P from PPPH. Inform. Process. Lett. 37 (1991) 149-153. | MR | Zbl
,[19] A survey on counting classes, in Proc. of the 5th Structure in Complexity Theory Conference, IEEE Computer Society Press (1990) 140-153. | MR
, and ,[20] 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] Easy sets and hard certificate schemes. Acta Inform. 34 (1997) 859-879. | MR | Zbl
, and ,[22] Strong self-reducibility precludes strong immunity. Math. Systems Theory 29 (1996) 535-548. | MR | Zbl
and ,[23] Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci. 24 (1983) 279-289. | MR | Zbl
and ,[24] Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). | MR | Zbl
and ,[25] Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput. 18 (1989) 392-408. | MR | Zbl
,[26] A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO, Theoret. Informatics Appl. 24 (1990) 229-240. | Numdam | MR | Zbl
,[27] A comparison of polynomial time reducibilities. Theoret. Comput. Sci. 1 (1975) 103-124. | MR | Zbl
, and ,[28] BPP and the polynomial hierarchy. Inform. Process. Lett. 17 (1983) 215-217. | MR | Zbl
,[29] 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] 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.
and .[31] A note on balanced immunity. Math. Systems Theory 26 (1993) 157-167. | MR | Zbl
,[32] Hardness vs randomness. J. Comput. System Sci. 49 (1994) 149-167. | MR | Zbl
and ,[33] Computational Complexity. Addison-Wesley (1994). | MR | Zbl
,[34] 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
and ,[35] 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] On closure properties of bounded two-sided error complexity classes. Math. Systems Theory 28 (1995) 229-243. | MR | Zbl
and ,[37] 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] Immunity and simplicity for exact counting and other counting classes. Technical Report TR 679, University of Rochester, Rochester, NY (1998).
,[39] Immunity, relativization, and nondeterminism. SIAM J. Comput. 13 (1984) 329-337. | Zbl
and ,[40] 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] Borel sets and circuit complexity, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 61-69.
,[42] A complexity theoretic approach to randomness, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 330-335.
,[43] 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] The polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977) 1-22. | MR | Zbl
,[45] PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20 (1991) 865-877. | MR | Zbl
,[46] Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput. 21 (1992) 316-328. | MR | Zbl
and ,[47] Structural Properties of the Counting Hierarchies. PhD thesis, Universitat Politècnica de Catalunya, Barcelona (1988).
,[48] Complexity classes defined by counting quantifiers. J. Assoc. Comput. Mach. 38 (1991) 753-774. | MR | Zbl
,[49] Structural Concepts in Relativised Hierarchies. PhD thesis, Universiteit van Amsterdam, Amsterdam, The Netherlands (1986).
,[50] Simplicity, immunity, relativizations and nondeterminism. Inform. and Comput. 80 (1989) 1-17. | MR | Zbl
and ,[51] The complexity of combinatorial problems with succinct input representations. Acta Inform. 23 (1986) 325-356. | MR | Zbl
,[52] Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977) 23-33. | MR | Zbl
,[53] 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.
,