Immunity and Simplicity for Exact Counting and Other Counting Classes
Institut für Informatik,
07740 Jena, Germany; firstname.lastname@example.org.
Accepted: March 1999
Ko  and Bruschi  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, , and ⊕P in all possible pairwise combinations. Our main result is that there is an oracle A relative to which contains a set that is immune BPP⊕P. In particular, this set is immune to PHA and to ⊕PA. Strengthening results of Torán  and Green , we also show that, in suitable relativizations, NP contains a -immune set, and ⊕P contains a PPPH-immune set. This implies the existence of a -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  circuit lower bound for majority.
Mathematics Subject Classification: 68Q15 / 68Q10 / 03D15
Key words: Computational complexity / immunity / counting classes / relativized computation / circuit lower bounds.
© EDP Sciences, 1999