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

摘要

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 (2k -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).