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
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
