Approximating values and solutions of NP-optimization problems: concepts and examples

We shape a formal framework for distinguishing the behaviour of constructive and non-constructive polynomial time approximation algorithms for NP optimization problems. We introduce a new class, called SubNPO (sub-problems of NPO), that includes NPO and also some other problems used in recent works. For this class, we define two types of approximation algorithms: the constructive ones and the non-constructive ones. For both cases we extend the notions of approximation level, of approximation-preserving' reductions and of related completeness. Then, we devise, under a completeness hypothesis, an equivalence result between constructive approximation and the non-constructive one. It generalizes to the case of polynomial time approximation a famous result of A. Paz and S. Moran. We finally point out some cases where both points of view differ from each other. In particular, we show that several problems, known to be complete for polynomial time constructive approximation, are not complete for the non-constructive one.