Structure in approximation classes

The study of the approximability properties of NP-hard optimization problem s has recently made great advances mainly due to the results obtained in th e field of proof checking. The last important breakthrough proves the APX-c ompleteness of several important optimization problems and thus reconciles "two distinct views of approximation classes: syntactic and computational" [S. Khanna et al., in Proc. 35th IEEE Symp. on Foundations of Computer Scie nce, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819-830]. In this paper we obtain new results on the structure of several computationall y-defined approximation classes. In particular, after defining a new approx imation preserving reducibility to be used for as many approximation classe s as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we s tate new connections between the approximability properties and the query c omplexity of NPO problems.