P-SELECTIVITY - INTERSECTIONS AND INDEXES

The P-selective sets (Selman, 1979) are those sets for which there is a polynomial-time algorithm that, given any two strings, determines wh ich is ''more likely'' to belong to the set: if either of the strings is in the set, the algorithm chooses one that is in the set. We prove that, for each k, the k-ary Boolean connectives under which the P-sele ctive sets are closed are exactly those that are either completely deg enerate or almost-completely degenerate. We determine the complexity o f the index set of the r.e. P-selective sets - Sigma(3)(0)-complete.