Class Description

OptP: Optimum Polynomial-Time

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.

Linked From

span-P: Span Polynomial-Time

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.

More about...