Quantifiers and approximation (Q1208413)

The paper studies the relation between approximability of combinatorial optimization problems and their logical description in terms of second order formulas over finite structures. The origin of this theory is \textit{Fagin}'s observation that problems in NP are exactly the generalized spectra of second order formulas over finite structures of the following type: the formula starts out with a single second order existential quantifier, followed by a \(\Sigma_ 2\) prefix and a quantifier free body. Optimization problems can be expressed by exchanging the second order existential quantification by a maximization (or minimization) over the same sort of sets. \textit{C. H. Papadimitriou} and \textit{M. Yanakakis} [J. Comput. Syst. Sci. 43, No. 3, 425-440 (1991; Zbl 0765.68036)] have introduced the class MAX NP consisting of those optimization problems for which the first order part of the defining formula is in fact a \(\Sigma_ 1\) formula. Subsequently they have shown that these problems can be approximated up to some positive fraction. They left open how large a fraction of the relevant optimization problems belong to the class MAX NP. The authors show by a logical technique that some problems (including the MAX CLIQUE problem) don't belong to MAX NP; they start from the hypothesis that they do and prove a contradiction by creating instances where the logical expression would yield an optimal value clearly different from the true combinatorial one. Subsequently they introduce the class MAX \(\Pi_ 1\) of problems defined by second order maximization with a \(\Pi_ 1\) formula; MAX CLIQUE belongs to this class. They obtain also complete problems for MAX \(\Pi_ 1\) under \(A\)- and \(P\)-reductions (reductions which preserve the quality of feasible solutions up to some degree of approximateness). A subclass RMAX\((k)\) is introduced which is obtained by a syntactic restriction (involving an integral parameter \(k)\) on the body of the formula. MAX CLIQUE and related problems have the interesting property that they either can't be approximated at all or can be approximated up to an arbitrary degree of quality. The property is caused by another property introduced by the authors which they call self-improvability. It is therefore interesting to observe that MAX CLIQUE is complete for RMAX(2) under quality preserving \(A\)-reductions and that therefore this property extends to the entire class of RMAX(2) reductions. While the paper was being processed for publication the world has learned the true state of affairs on the approximability of MAX CLIQUE: \textit{J. Arora ea}. have shown that MAX CLIQUE can't be approximated at all unless P=NP.