The class of functions computable by taking the maximum (or minimum) of the output values over all accepting paths of an NP machine. OptP[f(n)] restricts the size of the output to f(n) bits.
Defined in [Kre88].
Contrast with FNP.
MaxSat that returns the number of satisfied clauses, Clicque that returns the size of the clique, Chromatic Number are OptP[log n]-complete.
The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NP machine.
Defined in [KST+89], where it is also shown that span-P contains #P and OptP; and that span-P = #P if and only if UP = NP.