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.