\input zb-basic
\input zb-ioport
\iteman{io-port 00985665}
\itemau{Rao, Rajesh P.N.}
\itemti{A note on P-selective sets and closeness.}
\itemso{Inf. Process. Lett. 54, No.3, 179-185 (1995).}
\itemab
Summary: We investigate the class of sets that form sparse symmetric differences with \text{P}-selective sets. Intuitively, this class (denoted by \text{PSEL-close}) comprises of sets that can, in a certain sense, be approximated by \text{P}-selective sets. A primary motivation behind the introduction of this new class is to unify the separate approaches that have been undertaken for sparse and \text{P}-selective sets. In order to establish \text{PSEL-close} as a distinct class, we first prove a theorem separating it from both the encompassing class of \text{P}/\text{poly} and the subclasses of \text{P}-selective and sparse sets. We then prove that no $\le_{m}^{p}$-hard set for \text{E} can be in \text{PSEL-close}. The proof of this theorem relies on techniques from the work of Berman and Hartmanis (1977) and Sch\"oning (1986), and generalizes their results in a straightforward manner.
\itemrv{~}
\itemcc{}
\itemut{Computational complexity; Sparse sets; P-selective sets; Closeness}
\itemli{doi:10.1016/0020-0190(95)00038-E}
\end