Immunity and simplicity for exact counting and other counting classes

 Access to full text

 Full (PDF)

1. [1] T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP question. SIAM J. Comput. 4 (1975) 431-442. Zbl0323.68033MR395311
2. [2] J. Balcázar, Simplicity, relativizations and nondeterminism. SIAM J. Comput. 14 (1985) 148-157. Zbl0567.68027MR774935
3. [3] J. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I. EATCS Monographs in theoretical computer science. Springer-Verlag (1988). Zbl0638.68040MR1047862
4. [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.68053MR951339
5. [5] R. Beigel, Relativized counting classes: Relations among thresholds, parity, and mods. J. Comput. System Sci. 42 (1991) 76-96. Zbl0717.68031MR1093301
6. [6] R. Beigel, Perceptrons, PP, and the polynomial hierarchy. Computational Complexity 4 (1994) 339-349. Zbl0829.68059MR1313534
7. [7] R. Beigel, R. Chang and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies. Math. Systems Theory 26 (1993) 293-310. Zbl0776.68043MR1209999
8. [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. Zbl0454.68030MR605606
9. [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. MR1758134
10. [10] D. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. Zbl0754.68049MR1186181
11. [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.68050MR1174734
12. [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.68039MR1097013
13. [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. Zbl0766.68038MR1139093
14. [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. [15] M. Furst, J. Saxe and M. Sipser, Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory 17 (1984) 13-27. Zbl0534.94008MR738749
16. [16] J. Gill, Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977) 675-695. Zbl0366.02024MR464691
17. [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.68054MR847902
18. [18] F. Green, An oracle separating ⊕P from PPPH. Inform. Process. Lett. 37 (1991) 149-153. Zbl0714.68032MR1095698
19. [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. MR1097665
20. [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. [21] L. Hemaspaandra, J. Rothe and G. Wechsung, Easy sets and hard certificate schemes. Acta Inform. 34 (1997) 859-879. Zbl0883.68072MR1480239
22. [22] L. Hemaspaandra and M. Zimand, Strong self-reducibility precludes strong immunity. Math. Systems Theory 29 (1996) 535-548. Zbl0857.68046MR1397918
23. [23] S. Homer and W. Maass, Oracle dependent properties of the lattice of NP sets. Theoret. Comput. Sci. 24 (1983) 279-289. Zbl0543.03024MR716824
24. [24] J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). Zbl0426.68001MR645539
25. [25] K. Ko, Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput. 18 (1989) 392-408. Zbl0679.68088MR986675
26. [26] K. Ko, A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO, Theoret. Informatics Appl. 24 (1990) 229-240. Zbl0701.68032MR1072992
27. [27] R. Ladner, N. Lynch and A. Selman, A comparison of polynomial time reducibilities. Theoret. Comput. Sci. 1 (1975) 103-124. Zbl0321.68039MR395319
28. [28] C. Lautemann, BPP and the polynomial hierarchy. Inform. Process. Lett. 17 (1983) 215-217. Zbl0515.68042MR742072
29. [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. Zbl0933.03046MR1097674
30. [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. [31] H. Müller, A note on balanced immunity. Math. Systems Theory 26 (1993) 157-167. Zbl0771.68053MR1196155
32. [32] N. Nisan and A. Wigderson, Hardness vs randomness. J. Comput. System Sci. 49 (1994) 149-167. Zbl0821.68057MR1293639
33. [33] C. Papadimitriou, Computational Complexity. Addison-Wesley (1994). Zbl0833.68049MR1251285
34. [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. Zbl0506.68039
35. [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. Zbl0632.94030MR897705
36. [36] K. Regan and J. Royer, On closure properties of bounded two-sided error complexity classes. Math. Systems Theory 28 (1995) 229-243. Zbl0827.68046MR1316600
37. [37] J. Rothe, Some closure properties of GAP-definable classes. Technical Report TR Math/93/6, Friedrich-Schiller-Universität Jena, Jena, Germany (1993). 
38. Appeared as part of: A promise class at least as hard as the polynomial hierarchy. J. Comput. Inform. 1 (1995) 92-107. MR1647454
39. [38] J. Rothe, Immunity and simplicity for exact counting and other counting classes. Technical Report TR 679, University of Rochester, Rochester, NY (1998). Zbl0946.68051MR1707968
40. [39] U. Schöning and R. Book, Immunity, relativization, and nondeterminism. SIAM J. Comput. 13 (1984) 329-337. Zbl0558.68039
41. [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. 
42. [41] M. Sipser, Borel sets and circuit complexity, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 61-69. 
43. [42] M. Sipser, A complexity theoretic approach to randomness, in Proc. of the 15th ACM Symposium on Theory of Computing (1983) 330-335. 
44. [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. 
45. [44] L. Stockmeyer, The polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977) 1-22. Zbl0353.02024MR438810
46. [45] S. Toda, PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20 (1991) 865-877. Zbl0733.68034MR1115655
47. [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.68055MR1154526
48. [47] J. Torán, Structural Properties of the Counting Hierarchies. PhD thesis, Universitat Politècnica de Catalunya, Barcelona (1988). 
49. [48] J. Torán, Complexity classes defined by counting quantifiers. J. Assoc. Comput. Mach. 38 (1991) 753-774. Zbl0799.68080MR1125929
50. [49] L. Torenvliet, Structural Concepts in Relativised Hierarchies. PhD thesis, Universiteit van Amsterdam, Amsterdam, The Netherlands (1986). 
51. [50] L. Torenvliet and P. van Emde Boas, Simplicity, immunity, relativizations and nondeterminism. Inform. and Comput. 80 (1989) 1-17. Zbl0664.68049MR978058
52. [51] K. Wagner, The complexity of combinatorial problems with succinct input representations. Acta Inform. 23 (1986) 325-356. Zbl0621.68032MR853581
53. [52] C. Wrathall, Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977) 23-33. Zbl0366.02031MR438811
54. [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.