**Authors:** Amihood Amir, Richard Beigel, and William Gasarch

**Abstract:**
We show that if there is a polynomial-time algorithm that tests
*k*(*n*) = O(log*n*) points for membership in a set *A*
by making only *k*(*n*) - 1*X*, then *A* belongs to NP/poly and to co-NP/poly
(if *k*(*n*) = O(1) then *A* belongs to P/poly). In
particular, *k*(*n*) = O(log*n*) queries to an NP-complete set
(*k*(*n*) = O(1) queries to an NP-hard set) are more
powerful than *k*(*n*) - 1*k*(*n*) points for membership in *A* by making
only *k*(*n*) - 1 adaptive queries to a set *X*, then
there is a correspondingly small circuit that decides membership in
*A* without an oracle.

We investigate the quantitatively stronger assumption that there is a
polynomial-time algorithm that tests 2^{k} strings for
membership in *A* by making only *k* queries to an oracle
*X*, and we derive qualitatively stronger conclusions about the
structure of *A*: namely, *A* cannot be self-reducible
unless *A* is in P, and *A* cannot be NP-hard unless P = NP.
Similar results hold for counting classes.

In addition, we investigate relationships between bounded-query computations, lowness and the p-degrees.