Implicit recursion-theoretic characterizations of counting classes

DOI10.1007/S00153-022-00828-4MaRDI QIDQ2085583zbMATH OpenOpenAlexFDO

Authors Ugo Dal Lago, Reinhard Kahle, 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

counting hierarchyfunction algebrasimplicit computational complexityrecursion-theoretic characterizations

Mathematics Subject Classification ID

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

Review text

\textit{L. G. Valiant} [Theor. Comput. Sci. 8, 189--201 (1979; Zbl 0415.68008)] introduced the class \(\#P\) of all functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Later \textit{K. W. Wagner} [Theor. Comput. Sci. 47, 131--147 (1986; Zbl 0637.03034)] introduced a hierarchy of counting functions FCH by allowing queries to functions of the previous level as follows: the level \(0\) coincides with the class of functions FPTIME introduced by \textit{S. Bellantoni} and \textit{S. Cook} [Comput. Complexity 2, No. 2, 97--110 (1992; Zbl 0766.68037)], and for \(k>0\), \(\# P_k=(\#P)^{\#P_{k-1}}\), FCH =\(\bigcup_{k\ge 0}\{\# P_k\}\). In particular, \(\# P_1=\#P\). Here for classes of functions \(\mathcal{F}\) and \(\mathcal{G}\), \(\mathcal{F}^{\mathcal{G}}\) denotes the class of all functions which can be computed with \(\mathcal{F}\) resources but allowing oracle access to functions from \(\mathcal{G}\). \par In the paper under review, the authors give recursion-theoretic characterizations of all the levels \(\{\# P_k\}_{k\in \mathbb{N}}\), and of FCH itself.

Recommendations

• Recursion theoretic characterizations of complexity classes of counting functions
• Some observations on the connection between counting and recursion
• Polynomial Space Counting Problems
• Descriptive complexity of \(\#\)P functions
• The counting hierarchy in binary notation

Cites work

• A new recursion-theoretic characterization of the polytime functions
• A recursion-theoretic approach to NP
• Applicative theories for the polynomial hierarchy of time and its levels
• Characterizing NC with tier 0 pointers
• Characterizing PSPACE with pointers
• scientific article; zbMATH DE number 4160708 (Why is no real title available?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• scientific article; zbMATH DE number 7724208 (Why is no real title available?)
• Monotonicity constraints in characterizations of PSPACE
• Polytime, combinatory logic and positive safe induction
• Recursion theoretic characterizations of complexity classes of counting functions
• Separating NC along the \(\delta\) axis
• Some observations on the connection between counting and recursion
• The complexity of computing the permanent
• The polynomial hierarchy of functions and its levels
• The power of the middle bit of a \(\#\)P function
• The realm of primitive recursion
• Theories with self-application and computational complexity.
• Weak theories of operations and types

Cited in

(8)

• Some observations on the connection between counting and recursion
• Recursion theoretic characterizations of complexity classes of counting functions
• Recursion schemata for slowly growing depth circuit classes
• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
• Implicit complexity over an arbitrary structure: Quantifier alternations
• scientific article; zbMATH DE number 4041255 (Why is no real title available?)
• Read/write factorizable programs
• Enumerating error bounded polytime algorithms through arithmetical theories

This page was built for publication: Implicit recursion-theoretic characterizations of counting classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2085583)