Gap-definable counting classes
From MaRDI portal
Publication:1318473
DOI10.1016/S0022-0000(05)80024-8zbMath0802.68051MaRDI QIDQ1318473
Stephen A. Fenner, Stuart A. Kurtz, Lance J. Fortnow
Publication date: 11 December 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On the complexity of graph reconstruction, Restrictive Acceptance Suffices for Equivalence Problems, UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, On the power of generalized Mod-classes, Relationships among $PL$, $\#L$, and the determinant, UP and the low and high hierarchies: A relativized separation, ANALYSIS OF QUANTUM FUNCTIONS, The size of SPP, Arithmetization: A new method in structural complexity theory, Lower bounds and the hardness of counting properties, Languages polylog-time reducible to dot-depth 1/2, On the autoreducibility of functions, Unambiguous computations and locally definable acceptance types, Nondeterministic \(NC^1\) computation, Upward separation for FewP and related classes, Recursion theoretic characterizations of complexity classes of counting functions, An oracle builder's toolkit, The complexity of the characteristic and the minimal polynomial., On the algebraic complexity of some families of coloured Tutte polynomials, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, Exact learning via teaching assistants, The counting complexity of group-definable languages, A second step towards complexity-theoretic analogs of Rice's Theorem, Relativized worlds with an infinite hierarchy, Tally NP sets and easy census functions., Isolation, matching, and counting uniform and nonuniform upper bounds, Complexity limitations on quantum computation, A complexity theory for feasible closure properties, Comparing action descriptions based on semantic preferences, Quantum and classical complexity classes: Separations, collapses, and closure properties, LWPP and WPP are not uniformly gap-definable, Error-bounded probabilistic computations between MA and AM, A common algebraic description for probabilistic and quantum computations
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
- On counting and approximation
- Turing machines with few accepting computations and low sets for PP
- The polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Computational Complexity of Probabilistic Turing Machines
- Graph isomorphism is low for PP
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness
- Counting classes: Thresholds, parity, mods, and fewness
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
