Implicit recursion-theoretic characterizations of counting classes (Q2085583)

\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.