Query-limited reducibilities
Richard Beigel · 1988
We study classes of sets and functions computable by algorithms that make a limited number of queries to an oracle. We distinguish between queries made in parallel (each question being independent of the answers to the others, as in a truth-table reduction) and queries made in serial (each question being permitted to depend on the answers to the previous questions, as in a Turing reduction). We define computability by a set of functions, and we show that it captures the information-theoretic aspects of computability by a fixed number of queries to an oracle. Using that concept, we prove a very powerful result, the Nonspeedup Theorem, which states that 2 n parallel queries to any fixed nonrecursive oracle cannot be answered by an algorithm that makes only n queries to any oracle whatsoever. This is the tightest general result possible. A corollary is the intuitively obvious, but nontrivial result that additional parallel queries to an oracle allow us to compute additional functions; t...