Terse, superterse, and verbose sets (Q1803657)

If \(f\) is a function and \(A\) is a set then \(f\leq_ TB\) means that \(f\) could be computed with an oracle to \(B\). This paper launches an investigation of how many queries to \(B\) are required. Let \(F^ A_ n(x_ 1,\ldots,x_ n)=\langle\chi_ A(x)_ 1,\ldots,\chi_ A(x_ n)\rangle\), where \(\chi_ 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. We show that the range of possible query savings is limited by the following theorem: \(F^ A_ n\) cannot be computed with only \(\lfloor\log n\rfloor\) queries to a set \(X\) unless \(A\) is recursive. 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_{2^ n-1}\) can be computed with \(n\) queries to \(A\). We show 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.