The basic ingredients of an optimization problem are the set of instances or input objects, the set of feasible solutions or output objects associated with any instance, and the measure defined for any feasible solution. On the analogy of the theory of NP-completeness, we are interested in studying a class of optimization problems whose feasible solutions are short and easy-to-recognize. To this aim, suitable constraints have to be introduced. We thus give the following definition.
An NP optimization problem A is a fourtuple (I,sol,m,goal) such that
The goal of an NPO problem with respect to an instance x is to find an optimum solution, that is, a feasible solution y such that
In the following, opt will denote the function mapping an instance x to the measure of an optimum solution.
An NPO problem is said to be polynomially bounded if a polynomial q exists such that, for any instance x and for any solution y of x, . The class NPO PB is the set of polynomially bounded NPO problems.