Class Description

P-Sel: P-Selective Sets

The class of decision problems for which there's a polynomial-time algorithm with the following property. Whenever it's given two instances, a "yes" and a "no" instance, the algorithm can always decide which is the "yes" instance.

Defined in [Sel79], where it was also shown that if NP is contained in P-Sel then P = NP.

There exist P-selective sets that are not recursive (i.e. not in R).

Linked From

NPMV-sel: NPMV Selective

Has the same relation to NPMV as P-Sel does to P.

Defined in [HHN+95].

More about...


NPMVt-sel: NPMVt Selective

Has the same relation to NPMVt as P-Sel does to P.

Defined in [HHN+95].

More about...


NPSV-sel: NPSV Selective

Has the same relation to NPSV as P-Sel does to P.

Defined in [HHN+95].

More about...


NPSVt-sel: NPSVt Selective

Has the same relation to NPSVt as P-Sel does to P.

Also known as NP-sel.

Defined in [HHN+95].

More about...