Authors: Richard Beigel, William Gasarch, John Gill, and James Owings
Abstract: Let A be a subset of the natural numbers, and let FAn(x1,...,xn) = χA(x1)...χA(xn), where χA is the characteristic function of A. An oracle Turing machine with oracle A could certainly compute FAn with n queries to A. There are some sets A (e.g., the halting set) for which FAn 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 FAn from A requires n queries. A set A is superterse if the computation of FAn from any set requires n queries. A set A is verbose if FA2n-1 can be computed with n queries to A. The range of possible query savings is limited by the following theorem: FAn 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