Relativized counting classes: Relations among thresholds, parity, and mods

DOI10.1016/0022-0000(91)90040-CzbMath0717.68031OpenAlexW2002323159MaRDI QIDQ2638771

Richard Beigel

Publication date: 1991

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(91)90040-c

zbMATH Keywords

separationsoraclerelativised complexity classes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (16)

The expressive power of voting polynomials ⋮ On relations between counting communication complexity classes ⋮ On MODkP Counting Degrees ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ Universally serializable computation ⋮ Relations among MOD-classes ⋮ On the acceptance power of regular languages ⋮ A note on Mod and generalised Mod classes ⋮ Modulo classes and logarithmic advice ⋮ On the power of enumerative counting ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Non-mitotic Sets ⋮ An oracle separating \(\oplus P\) from \(PP^{PH}\) ⋮ Non-mitotic sets

Cites Work

• The complexity of computing the permanent
• On the construction of parallel computers from various basis of Boolean functions
• The complexity of combinatorial problems with succinct input representation
• Complexity classes without machines: on complete languages for UP
• The polynomial-time hierarchy
• On the unique satisfiability problem
• 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
• Computational Complexity of Probabilistic Turing Machines
• On the power of parity polynomial time
• Counting classes: Thresholds, parity, mods, and fewness
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Relativized counting classes: Relations among thresholds, parity, and mods