Authors: Richard Beigel
Abstract: 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 2n 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; the same is true of serial queries.
We show that if k + 1 parallel queries to the oracle A can be answered by an algorithm that makes only k serial queries to any oracle B, then n parallel queries to the oracle A can be answered by an algorithm that makes only O(logn) parallel queries to a third oracle C.
We also consider polynomial time bounded algorithms that make a fixed
number of queries to an oracle. It has been shown that the Nonspeedup
Theorem does not apply in the polynomial time bounded framework.
However, we prove a Weak Nonspeedup Theorem, which states that if
2k parallel queries to the oracle A can be
answered by an algorithm that makes only k serial queries to
the oracle B, then any n parallel queries to the oracle
A can be answered by an algorithm that makes only