Class Description

NPSV: NP Single Value

The class of NPMV functions that are single-valued (i.e., such that every accepting path outputs the same value).

Defined in [BLS84].

Contains NPSVt.

P = NP if and only if FP = NPSV.

Linked From

NPMV: NP Multiple Value

The class of all (possibly partial, possibly multivalued) functions computed by an NP machine as follows: ignore the rejecting paths, and consider any output of an accepting path to be "one of the outputs."

Contains NPSV and NPMVt.

Defined in [BLS84].

Contrast with FNP.

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: NPSV Total

The class of all NPSV functions that are total (that is, defined on every input).

Contained in NPMVt.

More about...