Class Description

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.

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

The class of all (possibly multivalued) NPMV functions that are total (that is, defined for every input).

More about...


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.

More about...