A note on P-selective sets and closeness
Rajesh P. N. Rao · Information Processing Letters · 1995
We investigate the class of sets that form sparse symmetric differences with P-selective sets. Intuitively, this class (denoted by PSEL-close) comprises of sets that can, in a certain sense, be approximated by 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 P-selective sets. In order to establish PSEL-close as a distinct class, we first prove a theorem separating it from both the encompassing class of P/poly and the subclasses of P-selective and sparse sets. We then prove that no ⩽mp-hard set for E can be in PSEL-close. The proof of this theorem relies on techniques from the work of Berman and Hartmanis (1977) and Schöning (1986), and generalizes their results in a straightforward manner.