Implicit recursion-theoretic characterizations of counting classes.

We give recursion-theoretic characterizations of the counting class # 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 { # P k } k ∈ N of the counting hierarchy of functions FCH , which result from allowing queries to functions of the previous level, and FCH itself as a whole. This is done in the style of Bellantoni and Cook's safe recursion, and it places # P in the context of implicit computational complexity. Namely, it relates # P with the implicit characterizations of FPTIME (Bellantoni and Cook, Comput Complex 2:97–110, 1992) and FPSPACE (Oitavem, Math Log Q 54(3):317–323, 2008), by exploiting the features of the tree-recursion scheme of FPSPACE . [ABSTRACT FROM AUTHOR]