A note on bi-immunity and p-closeness of p-cheatable sets in P/poly

Abstract In this paper we study the interplay between three measures of polynomial time behavior in sets: p -cheatability, p -closeness, and membership in P/poly . First we construct (2 k -1 for k )- p -cheatable sets that are bi-immune with respect to all recursively enumerable sets. We show that the constructed sets are in P/poly , but can be constructed so that they are not p -close. In fact, they can be constructed so that they are not even recursively close. Next, we construct ( n for 2)- p -cheatable sets that are bi-immune with respect to arbitrarily difficult deterministic time classes. These sets are also in P/poly , and they also can be constructed so that they are not p -close. Finally, we construct a set that is ( n for 1)- p -cheatable but is not p -close, although it, too, is in P/poly . These results show that, although p -cheatable, P/poly , and p -close sets all exhibit some form of polynomial time behavior, the notions of p -cheatability and p -closeness are often orthogonal. In addition, the results on p -closeness answer conjectures made in Amir and Gasarch ( Inform. and Comput . 77 (1988), 37–56).