Reducibility Classes of p-Selective Sets

摘要

A set is P-selective if there is a polynomial-time semi-decision algorithm forthe 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.