Authors: Amihood Amir, Richard Beigel, and William Gasarch

Abstract: We show that if there is a polynomial-time algorithm that tests k(n) = O(logn) points for membership in a set A by making only k(n) - 1 adaptive queries to an oracle set 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(logn) queries to an NP-complete set (k(n) = O(1) queries to an NP-hard set) are more powerful than k(n) - 1 queries, unless the polynomial hierarchy collapses. Similarly, if there is a small circuit that tests 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.

Download Full Paper