| 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 PH A and to ⊕P A. 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 PP PH-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.
|
