Key points are not available for this paper at this time.
We investigate tile relationship between logical expressibility of NP optimization problems and their approximation properties. First sucll attempt was made by Papadimitriou and Yannakakis, who defined the class of NPO problems MAX NP. We show that many importaut optimization problems do not belong to MAX NP and that in fact there are problems in P which are not ill lk'IAX NP. The problems that we consider fit naturally in a new complexity class that we call MAX Ill.
Panconesi et al. (Mon,) studied this question.