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.
The
class NPO
is the set of all NP optimization problems.
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.
Viggo Kann