Portal de Periódicos da CAPES

Completeness in approximation classes

1989; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-51498-8_11

1611-3349

Pierluigi Crescenzi, Alessandro Panconesi,

Optimization and Search Problems

We introduce a formal framework for studying approximation properties of NP optimization (NPO) problems. The classes we consider are those appearing in the literature, namely the class of approximable problems within a constant ε (APX), the class of problems having a Polynomial-time Approximation Scheme (PAS) and the class of problems having a Fully Polynomial-time Approximation Scheme (FPAS). We define natural approximation preserving reductions and obtain completeness results for these classes. A complete problem in a class can not have stronger approximation properties unless P=NP. We also show that the degree structure of NPO allows intermediate degrees, that is, if P≠NP, there are problems which are neither complete nor belong to a lower class.