**Authors:** Richard Beigel, William Gasarch, John Gill, and James Owings

**Abstract:**
Let *A* be a subset of the natural numbers, and let
F_{A}^{n}(*x*_{1},...,*x*_{n})
=
χ_{A}(*x*_{1})...χ_{A}(*x*_{n}),
where χ_{A} is the characteristic function of
*A*. An oracle Turing machine with oracle *A* could
certainly compute F_{A}^{n} with
*n* queries to *A*. There are some sets *A* (e.g., the
halting set) for which F_{A}^{n} can be
computed with substantially fewer than *n* queries. One key
reason for this is that the questions asked to the oracle can depend
on previous answers, i.e., the questions are *adaptive*. We
examine when it is possible to save queries. A set *A* is
*terse* if the computation of
F_{A}^{n} from *A* *requires*
*n* queries. A set *A* is *superterse* if the
computation of F_{A}^{n} from any set
requires *n* queries. A set *A* is *verbose* if
F_{A}^{2n-1} can be computed with
*n* queries to *A*. The range of possible query savings is
limited by the following theorem:
F_{A}^{n} cannot be computed with only
log*n* queries to a set *X* unless *A* is recursive.
In addition we produce the following: (1) a verbose set in each
truth-table degree and a superterse set in each nonzero
truth-table degree; and (2) an r.e. verbose set in each
r.e. truth-table degree and an r.e. terse set in each nonzero
r.e. Turing degree.