Abstract

We give recursion-theoretic characterizations of the counting class \(\textsf {\#P} \), the class of those functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Moreover, we characterize in a recursion-theoretic manner all the levels \(\{\textsf {\#P} _k\}_{k\in {\mathbb {N}}}\) of the counting hierarchy of functions \(\textsf {FCH} \), which result from allowing queries to functions of the previous level, and \(\textsf {FCH} \) itself as a whole. This is done in the style of Bellantoni and Cook’s safe recursion, and it places \(\textsf {\#P} \) in the context of implicit computational complexity. Namely, it relates \(\textsf {\#P} \) with the implicit characterizations of \(\textsf {FPTIME} \) (Bellantoni and Cook, Comput Complex 2:97–110, 1992) and \(\textsf {FPSPACE} \) (Oitavem, Math Log Q 54(3):317–323, 2008), by exploiting the features of the tree-recursion scheme of \(\textsf {FPSPACE} \).