Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



ECCC BOOKS, LECTURES AND SURVEYS > QUERY LIMITED REDUCIBILITIES:

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 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 2k - 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



ISSN 1433-8092 | Imprint