On P-Selectivity and Closeness
Rajesh P. N. Rao · 1994
P/poly, the class of sets with polynomial size circuits, has been the subject of considerable study in complexity theory. Two important subclasses of P/poly are the class of sparse sets [6] and the class of P-selective sets [31]. A large number of results have been proved about both these classes but it has been observed (for example, [17]) that despite their similarity, proofs about one class generally do not translate easily to proofs regarding the other class. In this note, we propose to resolve this asymmetry by investigating the class PSEL-close of sets that are polynomially close to P-selective sets; by definition, PSEL-close includes both sparse sets and P-selective sets, thereby providing a unifying platform for proving results applicable to both. Intuitively, PSEL-close is the class of sets that can in a certain sense be approximated by P-selective sets. We prove several results separating PSEL-close from known classes within and including P/poly, and establish its location op...