The subclass of NPO problems for which the cost function is guaranteed always to be bounded by a polynomial in n (the input size).
See [ACG+99].
NPOPB equals the closure of MaxPB under PTAS reductions [CKS+99].
The subclass of MaxNP problems for which the cost function is guaranteed always to be bounded by a polynomial.
MinPB can be defined similarly.
Defined in [KT94].
The closure of MaxPB under PTAS reductions equals NPOPB [CKS+99].
The class of function problems of the form, "Find any n-bit string x that maximizes a cost function C(x), where C is computable in FP (i.e. polynomial-time)."
Defined in [ACG+99].