Implicit recursion-theoretic characterizations of counting classes

DOI10.1007/s00153-022-00828-4zbMath1506.03096OpenAlexW4225321823MaRDI QIDQ2085583

Reinhard Kahle, Ugo Dal Lago, Isabel Oitavem

Publication date: 18 October 2022

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-022-00828-4

zbMATH Keywords

implicit computational complexitycounting hierarchyfunction algebrasrecursion-theoretic characterizations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Read/write factorizable programs, Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• A recursion-theoretic approach to NP
• Some observations on the connection between counting and recursion
• The realm of primitive recursion
• A new recursion-theoretic characterization of the polytime functions
• Recursion theoretic characterizations of complexity classes of counting functions
• Polytime, combinatory logic and positive safe induction
• Theories with self-application and computational complexity.
• Separating NC along the \(\delta\) axis
• The power of the middle bit of a \(\#\)P function
• Applicative theories for the polynomial hierarchy of time and its levels
• The polynomial hierarchy of functions and its levels
• Monotonicity Constraints in Characterizations of PSPACE
• Characterizing PSPACE with pointers
• Characterizing NC with tier 0 pointers