Quantifiers and Approximation

Abstract

We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitriou and Yannakakis, who defined the class of NPO problems MAX NP. We show that many important optimization problems do not belong to MAX NP and that in fact there are problems in P which are not is MAXNP. The problems we consider fit naturally in a new complexity class that we call MAX II sub 1. We prove that several natural optimization problems are complete for MAX II sub 1 under approximation preserving reductions. All these complete problems are non-approximable unless P=NP. This motivates the definition of subclasses of MAX II sub 1 that only contain problems which are presumably easier with respect to approximation. In particular, the class that we call RMAX(2), contains approximable problems and problems like MAX CLIQUE that are not known to be non-approximable. We prove that MAX CLIQUE and other natural optimization problems are complete for RMAX(2). All the complete problems in RMAX(2) share the interesting property that they either are non-approximable or are approximable to any degree of accuracy.