Gap-definable counting classes
From MaRDI portal
Publication:1318473
DOI10.1016/S0022-0000(05)80024-8zbMath0802.68051OpenAlexW2083553352MaRDI QIDQ1318473
Lance J. Fortnow, Stephen A. Fenner, Stuart A. Kurtz
Publication date: 11 December 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80024-8
Related Items (46)
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ A complexity theory for feasible closure properties ⋮ Upward separation for FewP and related classes ⋮ Unnamed Item ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ The size of SPP ⋮ On the complexity of graph reconstruction ⋮ Unambiguous computations and locally definable acceptance types ⋮ The minimum oracle circuit size problem ⋮ Parameterised counting in logspace ⋮ An oracle builder's toolkit ⋮ Positive and negative proofs for circuits and branching programs ⋮ The complexity of the characteristic and the minimal polynomial. ⋮ Unnamed Item ⋮ On the power of generalized Mod-classes ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ Complexity limitations on quantum computation ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ The consequences of eliminating NP solutions ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ On the algebraic complexity of some families of coloured Tutte polynomials ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Comparing action descriptions based on semantic preferences ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Arithmetization: A new method in structural complexity theory ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ On the autoreducibility of functions ⋮ Lower bounds and the hardness of counting properties ⋮ LWPP and WPP are not uniformly gap-definable ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ On the hardness of the noncommutative determinant ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Unnamed Item ⋮ Graph isomorphism is low for PP ⋮ Nondeterministic \(NC^1\) computation ⋮ 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 ⋮ SELF-SPECIFYING MACHINES ⋮ A common algebraic description for probabilistic and quantum computations ⋮ Tally NP sets and easy census functions. ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Relativized worlds with an infinite hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Gap-definable counting classes
