NPO is defined to be the class of optimization problems whose decision versions are in NP.
I would like to get the complexity class of optimization problems whose decision versions are in P.
Is such a complexity class already defined?
1 Answer 1
This class is PO, i.e., those optimization problems where an optimal solution can be computed in polynomial time. It is known that if an optimization problem is in PO then its decision version is in P.
Explore related questions
See similar questions with these tags.