Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
From MaRDI portal
Publication:3990656
DOI10.1137/0221023zbMath0755.68055OpenAlexW2165676867MaRDI QIDQ3990656
Seinosuke Toda, Mitsunori Ogiwara
Publication date: 28 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/f2d2e0363d0d121063d8f514fade7642a8288ba7
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (40)
Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Complexity of counting the optimal solutions ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ On ACC ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ The size of SPP ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Uniform proofs of ACC representations ⋮ Algebraic methods and bounded formulas ⋮ Universally serializable computation ⋮ On the probabilistic degree of OR over the reals ⋮ On the power of deterministic reductions to C=P ⋮ Counting and enumerating preferred database repairs ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Complexity of Counting the Optimal Solutions ⋮ Parameterized random complexity ⋮ Two queries ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ Counting subset repairs with functional dependencies ⋮ On polynomial approximations to AC ⋮ On the acceptance power of regular languages ⋮ Modulo classes and logarithmic advice ⋮ The complexity of two problems on arithmetic circuits ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Complexity classes of equivalence problems revisited ⋮ Unnamed Item ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Dot operators ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Unnamed Item ⋮ Transducing Markov sequences ⋮ A note on the circuit complexity of PP ⋮ Tally NP sets and easy census functions. ⋮ On bounded-probability operators and C\(_ =\)P ⋮ Gap-definable counting classes ⋮ Relativized worlds with an infinite hierarchy ⋮ One complexity theorist's view of quantum computing
This page was built for publication: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
