Immunity and simplicity for exact counting and other counting classes
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, , 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...