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

Abstract: Let A be a subset of the natural numbers, and let F_Aⁿ(x₁,...,x_n) = χ_A(x₁)...χ_A(x_n), where χ_A is the characteristic function of A. An oracle Turing machine with oracle A could certainly compute F_Aⁿ with n queries to A. There are some sets A (e.g., the halting set) for which F_Aⁿ 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ⁿ from A requires n queries. A set A is superterse if the computation of F_Aⁿ 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ⁿ cannot be computed with only logn 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.

Download Full Paper