A note on the descriptive complexity of maximization problems (Q685495)

\textit{A. Panconesi} and \textit{D. Ranjan}, Quantifiers and approximation, in: Proc. 22 nd ACM STOC, 446-456 (1990)] have introduced, two classes called MAXII and RMAX(2). From the definition of such classes, it follows that the latter class is a subset of the former. On the other hand, \textit{P. G. Kolaitis} and \textit{M. N. Thakur} [Logical definability of NP optimization problems, Tech. Rept. UCSC-CRL-90-48, Computer and Information Sciences, University of California, Santa Cruz (1990); Approximation properties of NP minimization classes, in: Proc. 6th IEEE Structure in Complexity Theory Conf., 353-366 (1991) have proved some surprising relationships between classes of optimization problems whose optimum is definable using existential or universal first-order formulae. In particular, they have also proved that \(MAXNP\subset MAXII\). We improve that above inclusion by showing that \(MAXNP\subset RMAX(2)\). This is the best we can obtain in terms of \(RMAX(k)\) classes, in the sense that \(MAXNP\not\subset RMAX(1)\) unless \(P=NP\). Furthermore, a corollary of our result is the \(MAXNP\)-hardness of the MAX CLIQUE problem which has already been proved in [\textit{P. Crescenzi}, \textit{C. Fiorini} and \textit{R. Silvestri}, A note on the approximation of the MAX CLIQUE problem, Inform. Process. Lett 40, 1-5 (1991; Zbl 0751.68027)].