Authors: Amihood Amir, Richard Beigel, and William Gasarch
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
We investigate the quantitatively stronger assumption that there is a polynomial-time algorithm that tests 2k 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