Bi-immunity results for cheatable sets (Q920981)

A bounded query class contains sets and functions computable by algorithms that make a bounded number of queries to an oracle. These queries can be made in series or in parallel. A set A is called k- cheatable if there exists a set B such that \(2^ k\) parallel queries to A do not allow us to compute more functions than only k serial queries to B. A set A is immune for the class \({\mathcal C}\) if A contains no infinite subset that belongs to \({\mathcal C}\). A is bi-immune for \({\mathcal C}\) if A and \(\bar A\) are immune for \({\mathcal C}\). The paper studies bi-immunity properties for cheatable sets. Theorem 4.4 constructs 2-cheatable sets that are bi-immune for arbitrary time complexity classes. Theorem 5.5 shows that if a recursive set A is bi-immune for P then there exists a nontrivial 1-cheatable set that is polynomial time m-reducible to A. As a consequence, Theorem 5.6 shows that if NP contains a set that is bi- immune for P then NP contains a set that is not a polynomial-time Turing- equivalent to a self-reducible set. This result provides a plausible condition under which NP intersects a non-self-reducible polynomial time Turing degree and hence gives a partial answer to a question of Selman. In the last section it is proven that there exists a set that is k- cheatable but not (k-1)-cheatable, for each \(k\geq 1\).