Complexity classes defined by counting quantifiers
From MaRDI portal
Publication:4302854
DOI10.1145/116825.116858zbMath0799.68080OpenAlexW1989159237MaRDI QIDQ4302854
Publication date: 21 August 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/116825.116858
Related Items (33)
On relations between counting communication complexity classes ⋮ On closure properties of GapP ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Dependence logic with a majority quantifier ⋮ The effect of combination functions on the complexity of relational Bayesian networks ⋮ The minimum oracle circuit size problem ⋮ Universally serializable computation ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ On counting propositional logic and Wagner's hierarchy ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ On the power of generalized Mod-classes ⋮ The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ On the acceptance power of regular languages ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Graph isomorphism is low for PP ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ On the autoreducibility of functions ⋮ Lower bounds and the hardness of counting properties ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Dot operators ⋮ The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws ⋮ The ultra-weak Ash conjecture and some particular cases ⋮ Complexity results for probabilistic answer set programming ⋮ Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\) ⋮ Complexity results for structure-based causality. ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy
This page was built for publication: Complexity classes defined by counting quantifiers
