COMPLETENESS IN APPROXIMATION CLASSES

We introduce a formal framework for studying approximation properties of NP optimization (NPO) problems. The classes of approximable problems we consider are those appearing in the literature, namely the class of approximable problems within a constant ε (APX), and the class of problems having a polynomial time approximation scheme (PTAS). We define natural approximation preserving reductions and obtain completeness results in NPO, APX, and PTAS. A complete problem in a class cannot 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.