Immunity and Simplicity for Exact Counting and Other Counting Classes
From MaRDI portal
Abstract: 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 BPP^{ParityP}. In particular, this C_{=}P^A set is immune to PH^{A} and ParityP^{A}. Strengthening results of Tor'{a}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 PP^{PH}-immune set. This implies the existence of a C_{=}P^{B}-simple set for some oracle B, which extends results of Balc'{a}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.
Recommendations
- Immunity, simplicity, probabilistic complexity classes and relativizations
- Immunity and simplicity in relativizations of probabilistic complexity classes
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- A note on separating the relativized polynomial time hierarchy by immune sets
Cites work
- A comparison of polynomial time reducibilities
- A note on balanced immunity
- A note on separating the relativized polynomial time hierarchy by immune sets
- A relationship between difference hierarchies and relativized polynomial hierarchies
- A uniform approach to define complexity classes
- An oracle separating \(\oplus P\) from \(PP^{PH}\)
- BPP and the polynomial hierarchy
- Complete sets and the polynomial-time hierarchy
- Complexity classes defined by counting quantifiers
- Computational Complexity of Probabilistic Turing Machines
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Easy sets and hard certificate schemes
- Hardness vs randomness
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Immunity and simplicity in relativizations of probabilistic complexity classes
- Immunity, Relativizations, and Nondeterminism
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- On closure properties of bounded two-sided error complexity classes
- On the construction of parallel computers from various basis of Boolean functions
- Oracle-dependent properties of the lattice of NP sets
- Parity, circuits, and the polynomial-time hierarchy
- Perceptrons, PP, and the polynomial hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- PP is closed under truth-table reductions
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized counting classes: Relations among thresholds, parity, and mods
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- Simplicity, immunity, relativizations and nondeterminism
- Simplicity, Relativizations and Nondeterminism
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- Strong self-reducibility precludes strong immunity
- STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- The complexity of combinatorial problems with succinct input representation
- The polynomial-time hierarchy
Cited in
(6)- The robustness of LWPP and WPP, with an application to graph reconstruction
- Query-monotonic Turing reductions
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- Resource bounded immunity and simplicity
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
This page was built for publication: Immunity and Simplicity for Exact Counting and Other Counting Classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4265536)
