An implicit characterization of the class NP is given, without using any minimization scheme. This is the first purely recursion-theoretic formulation of NP.

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} \). (shrink)