**Authors:** Richard Beigel

**Abstract:**
An oracle *A* is *k*-*cheatable* if there is a
polynomial-time algorithm to determine the answers to
2^{k} 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.