Browse Reports

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 [Berman and Hartmanis, 1977] and the class of P-selective sets [Selman, 1979]. A large number of results have been proved about both these classes but it has been observed (for example, [Hemaspaandra et al., 1993]) that despite their similarity, proofs about one class generally do not translate easily to proofs regarding the other class. .pp 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 optimally in the extended low hierarchy. We illustrate the naturalness and usefulness of the class by examining the question of whether sets hard for NP or E can be PSEL-close; several well-known results are obtained as immediate corollaries.