Polynomial-Time Semi-Rankable Sets.
Lane A. Hemaspaandra, Mohammed Javeed Zaki, Marius Zimand · 1995
We study the polynomial-time semi-rankable sets (P-sr), the ranking analog of the P-selective sets. We prove that P-sr is a strict subset of the P-selective sets, and indeed that the two classes differ with respect to closure under complementation, closure under union with P sets, closure under join with P sets, and closure under P-isomorphism. While P=poly is equal to the closure of P-selective sets under polynomial-time Turing reductions, we build a tally set that is not polynomial-time reducible to any P-sr set. We also show that though P-sr falls between the P-rankable and the weakly-P-rankable sets in its inclusiveness, it equals neither of these classes. Key words: semi-feasible sets, P-selectivity, ranking, closure properties, NNT. 1 Introduction In the late 1970s, Selman [Sel79] defined the semi-feasible (i.e., P-selective) sets, which are the polynomial-time analog of the Jockusch's [Joc68] semi-recursive sets. Recently, there has been an intense renewal of interest in the P...