Authors: Richard Beigel
Abstract: An oracle A is k-cheatable if there is a polynomial-time algorithm to determine the answers to 2k parallel queries to A from the answers to only k queries to some other oracle B. It is known that 1-cheatable sets cannot be bi-immune for P. In contrast, we construct 2-cheatable sets that are bi-immune for arbitrary time complexity classes. In addition, for each k, we construct a set that is (k+1)-cheatable, but not k-cheatable; we show that this separation does not hold with bi-immunity. We show that if a recursive set A is bi-immune for P then there exists an infinite 1-cheatable set that is polynomial-time m-reducible to A. Consequently if NP contains a set that is bi-immune for P then NP contains a set that is not polynomial-time Turing-equivalent to a self-reducible set.