1998/09/01 by Joerg Rothe, Rothe, Joerg
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.2 #F.1.3 #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/9809001
20 pages
arxiv created 1998/09/01 · openalex publication_date 1998/09/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Ko [RAIRO 24, 1990] and Bruschi [TCS 102, 1992] showed that in some relativized world, PSPACE (in fact, ParityP) 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, C=P, and ParityP in all possible pairwise combinations. Our main result is that there is an oracle A relative to which C=P contains a set that is immune to BPPParityP. In particular, this C=PA set is immune to PHA and ParityPA. Strengthening results of Torán [J.ACM 38, 1991] and Green [IPL 37, 1991], we also show that, in suitable relativizations, NP contains a C=P-immune set, and ParityP contains a PPPH-immune set. This implies the existence of a C=PB-simple set for some oracle B, which extends results of Balcázar et al. [SIAM J.Comp. 14, 1985; RAIRO 22, 1988] and provides the first example of a simple set in a class not known to be contained in PH. Our proof technique requires a circuit lower bound for ``exact counting'' that is derived from Razborov's [Mat. Zametki 41, 1987] lower bound for majority.