Terse, superterse, and verbose sets
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.
- Polynomial terse sets
- Bounded query classes and the difference hierarchy
- Nondeterministic bounded query reducibilities
- Bounded queries to SAT and the Boolean hierarchy
- Weakly semirecursive sets and r.e. orderings
- Learning via queries and oracles
- Extremes in the degrees of inferability
- Learning recursive functions from approximations
- Binary search and recursive graph problems
- Some connections between bounded query classes and non-uniform complexity.
- Enumerative counting is hard
- On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
- Quantifying the amount of verboseness
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- On the structures inside truth-table degrees
- scientific article; zbMATH DE number 1678392 (Why is no real title available?)
- A proof of Beigel's cardinality conjecture
- scientific article; zbMATH DE number 517081 (Why is no real title available?)
- scientific article; zbMATH DE number 1361501 (Why is no real title available?)
- The complexity of ODDnA
- The power of frequency computation
- Unbounded search and recursive graph problems
- Enumerations of the Kolmogorov function
- The communication complexity of enumeration, elimination, and selection
- Frequency computation and bounded queries
- On quasilinear-time complexity theory
- Choosing, agreeing, and eliminating in communication complexity
- On adaptive versus nonadaptive bounded query machines
- The complexity of finding SUBSEQ(A)
- Bi-immunity results for cheatable sets
- On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
This page was built for publication: Terse, superterse, and verbose sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803657)
