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

Judy Goldsmith; Deborah Joseph; Paul Young

doi:10.1016/0022-0000(93)90008-K

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

Judy Goldsmith
, Deborah Joseph
, Paul Young

Producción científica: Article › revisión exhaustiva

5 Citas (Scopus)

Resumen

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

Idioma original	English
Páginas (desde-hasta)	349-362
Número de páginas	14
Publicación	Journal of Computer and System Sciences
Volumen	46
N.º	3
DOI	https://doi.org/10.1016/0022-0000(93)90008-K
Estado	Published - 1993

Nota bibliográfica

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.

Financiación

* 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.

Financiadores	Número del financiador
AT&T Bell Laboratories
National Science Foundation (NSF)	DCR-8402375

ASJC Scopus subject areas

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

Acceder al documento

10.1016/0022-0000(93)90008-K

Otros archivos y enlaces

Citar esto

@article{1c192215e09b48f2995131e660a44348,

title = "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 (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).",

author = "Judy Goldsmith and Deborah Joseph and Paul Young",

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.",

year = "1993",

doi = "10.1016/0022-0000(93)90008-K",

language = "English",

volume = "46",

pages = "349--362",

number = "3",

}

TY - JOUR

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

AU - Goldsmith, Judy

AU - Joseph, Deborah

AU - Young, Paul

N1 - 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.

PY - 1993

Y1 - 1993

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

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

UR - https://www.scopus.com/pages/publications/28044471610

UR - https://www.scopus.com/pages/publications/28044471610#tab=citedBy

U2 - 10.1016/0022-0000(93)90008-K

DO - 10.1016/0022-0000(93)90008-K

M3 - Article

AN - SCOPUS:28044471610

SN - 0022-0000

VL - 46

SP - 349

EP - 362

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -

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

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto