Counting classes: Thresholds, parity, mods, and fewness
From MaRDI portal
Publication:5896571
DOI10.1007/3-540-52282-4_31zbMath0729.68023OpenAlexW4243280876MaRDI QIDQ5896571
Richard Beigel, John Gill, Ulrich Hertrampf
Publication date: 1990
Published in: STACS 90 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-52282-4_31
Related Items (17)
A complexity theory for feasible closure properties ⋮ On closure properties of GapP ⋮ Non-deterministic communication complexity with few witnesses ⋮ Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Structure and importance of logspace-MOD class ⋮ Unambiguous computations and locally definable acceptance types ⋮ Universally serializable computation ⋮ Locally definable acceptance types for polynomial time machines ⋮ Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes ⋮ A note on Mod and generalised Mod classes ⋮ Arithmetization: A new method in structural complexity theory ⋮ Reductions to sets of low information content ⋮ Graph isomorphism is low for PP ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Gap-definable counting classes
This page was built for publication: Counting classes: Thresholds, parity, mods, and fewness