Reductibility classes of P-selective sets
Lane A. Hemaspaandra, Albrecht Hoene, Mitsunori Ogihara · Theoretical Computer Science · 1996
A set is P-selective (Selman, 1979) if there is a polynomial-time semidecision algorithm for the set — an algorithm that given any two strings decides which is “more likely” to be in the set. This paper establishes a strict hierarchy among the various reductions and equivalences to P-selective sets.