Abstract On Counting and Approximation
Johannes Köbler, Uwe Schöning, and Jacobo Toran
Abstract: We introduce a new class of functions, called span
functions which count the different output values that occur at the
leaves of the computation tree associated with a nondeterministic
polynomial time Turing machine transducer. This function class has
natural complete problems; it is placed between Valiant's classes #P
and #NP, and containes both Goldberg and Sipser's ranking functions
for sets in NP, and Krentel's optimization functions. We show that it
is unlikely that the span functions coincide with any of the mentioned
function classes. A probabilistic approximation method (using an
oracle in NP) is presented to approximate span functions up to any
desired degree of accuracy. This approximation method is based on
universal hashing and it never underestimates the correct value of the
approximated function.