RECURSION THEORETIC CHARACTERIZATIONS OF COMPLEXITY CLASSES OF COUNTING FUNCTIONS

There has been a great effort in giving machine-independent, algebraic characterizations of complexity classes, especially of functions. Ast onishingly, no satisfactory characterization of the prominent class #P is known up to now. Here, we characterize #P as the closure of a set of simple arithmetical functions under summation and weak product. Bas ed on that result, the hierarchy of counting functions, which is the c losure of #P under substitution, is characterized, remarkably without using the operator of substitution, since we can show that in the cont ext of this hierarchy the operation of modified subtraction is as powe rful as substitution. This leads us to a number of consequences concer ning closure of #P under certain arithmetical operations. Analogous re sults are achieved for the class Gap-P which is the closure of #P unde r subtraction.