Counting classes: Thresholds, parity, mods, and fewness

DOI10.1016/0304-3975(92)90084-SzbMath0760.68028OpenAlexW1736584826MaRDI QIDQ5905584

John Gill, Richard Beigel

Publication date: 16 January 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90084-s

zbMATH Keywords

PPpolynomialspolynomial timeunique solutionscounting classes\(\#P\)FewMOD\(_ k P\)PARITYP

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Stathis Zachos at 70!, NL-printable sets and nondeterministic Kolmogorov complexity, On MODkP Counting Degrees, On ACC, Representing Boolean functions as polynomials modulo composite numbers, On helping by parity-like languages, Autoreducibility, mitoticity, and immunity, On the power of generalized Mod-classes, On a theorem of Razborov, Relations among MOD-classes, Unnamed Item, On the acceptance power of regular languages, Modulo classes and logarithmic advice, The complexity of two problems on arithmetic circuits, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, On the power of parity polynomial time, Graph isomorphism is low for PP, NL-printable sets and Nondeterministic Kolmogorov Complexity, Quantum and classical complexity classes: Separations, collapses, and closure properties, Unnamed Item, Unnamed Item, On the hardness of the noncommutative determinant, On Existentially First-Order Definable Languages and Their Relation to NP, Tally NP sets and easy census functions., Gap-definable counting classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Relations among MOD-classes
• Strong nondeterministic polynomial-time reducibilities
• On the construction of parallel computers from various basis of Boolean functions
• NP is as easy as detecting unique solutions
• The complexity of combinatorial problems with succinct input representation
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• Relativized counting classes: Relations among thresholds, parity, and mods
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Constant Depth Reducibility
• On the unique satisfiability problem
• Relativized Questions Involving Probabilistic Algorithms
• Computational Complexity of Probabilistic Turing Machines
• Complexity classes defined by counting quantifiers
• On the power of parity polynomial time