### Richard Beigel:

## Query-limited Reducibilities

Ph.D. Dissertation

Stanford University, 1995

**Download**

**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
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; 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(log*n*) 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
2^{k} 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
2^{k} - 1 of the same queries to *A*. A corollary
is that if *A* is NP-hard and P ≠ NP, then extra parallel
queries to *A* allow us to compute extra functions in polynomial
time; the same is true of serial queries.

Download Full Paper