## 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).

Original language | English |
---|---|

Pages (from-to) | 349-362 |

Number of pages | 14 |

Journal | Journal of Computer and System Sciences |

Volume | 46 |

Issue number | 3 |

DOIs | |

State | Published - 1993 |

### Bibliographical note

Funding Information:* This work was supported in part by the National Science Foundation under Grant DCR-8402375, as well as by a grant from AT & T Bell Laboratories. The work was done while the first author was a graduate student at the University of Wisconsin-Madison. The work reported here provides proofs for, and in some cases slightly extends, some of the material in [GJY-87a, GJY-87b] reported at the Second Annual Structure in Complexity Theory Conference.

### Funding

* This work was supported in part by the National Science Foundation under Grant DCR-8402375, as well as by a grant from AT & T Bell Laboratories. The work was done while the first author was a graduate student at the University of Wisconsin-Madison. The work reported here provides proofs for, and in some cases slightly extends, some of the material in [GJY-87a, GJY-87b] reported at the Second Annual Structure in Complexity Theory Conference.

Funders | Funder number |
---|---|

AT&T Bell Laboratories | |

National Science Foundation (NSF) | DCR-8402375 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics