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

Judy Goldsmith, Deborah Joseph, Paul Young

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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

Original languageEnglish
Pages (from-to)349-362
Number of pages14
JournalJournal of Computer and System Sciences
Volume46
Issue number3
DOIs
StatePublished - 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.

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'A note on bi-immunity and p-closeness of p-cheatable sets in P/poly'. Together they form a unique fingerprint.

Cite this