Recursion theoretic characterizations of complexity classes of counting functions
From MaRDI portal
Publication:1365942
DOI10.1016/0304-3975(95)00237-5zbMath0877.68059OpenAlexW2068563862MaRDI QIDQ1365942
Heribert Vollmer, Klaus W. Wagner
Publication date: 10 September 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00237-5
Related Items (3)
Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting) ⋮ Nondeterministic \(NC^1\) computation ⋮ Implicit recursion-theoretic characterizations of counting classes
Cites Work
- The complexity of computing the permanent
- Arithmetization: A new method in structural complexity theory
- A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
- Some observations on the connection between counting and recursion
- An arithmetical characterization of NP
- Relative complexity of checking and evaluating
- Gap-definable counting classes
- On closure properties of GapP
- Complexity classes of optimization functions
- A complexity theory for feasible closure properties
- PP is as Hard as the Polynomial-Time Hierarchy
- Languages that Capture Complexity Classes
- Computational Complexity of Probabilistic Turing Machines
- Expressibility and Parallel Complexity
- Arithmetical problems and recursively enumerable predicates
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Recursion theoretic characterizations of complexity classes of counting functions
