**Authors:** Richard Beigel, William Gasarch, and Efim Kinber

**Abstract:**
There have been several papers over the last ten years that consider
the number of queries needed to compute a function as a measure of its
complexity. The following function has been studied extensively in
that light:
F_{A}^{a}(*x*_{1}, ... , *x*_{a})
=
*A*(*x*_{1})...*A*(*x*_{a}). We
are interested in the complexity (in terms of the number of queries)
of approximating F_{A}^{a}. Let *b*
≤ *a* and let *f* be any function such that
F_{A}^{a}(*x*_{1}, ... , *x*_{a})
and *f*(*x*_{1}, ... , *x*_{a})*b* bits. For a general set *A* we have
matching upper and lower bounds on *f* that depend on coding
theory. These are applied to get exact bounds for the case where
*A* is semirecursive, *A* is superterse, and (assuming P
≠ NP) *A* = SAT. We obtain exact bounds when *A* is the
halting problem using different methods.