A note on the descriptive complexity of maximization problems
\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)].
- Comparative versus quantitative truthlikeness definitions: Reply to Thomas Mormann
- scientific article; zbMATH DE number 1322635
- Probabilistic properties of approximation problems
- A general set theoretic approximation framework
- REASONING WITH FUZZY QUANTIFIED STATEMENTS: PART II
- On optimal approximations of arbitrary relations by partial orders
- Property-driven rough sets approximations of relations
- Approximations of arbitrary relations by partial orders
- scientific article; zbMATH DE number 4047069
- Local and Global Approximations for Incomplete Data
- A note on the approximation of the MAX CLIQUE problem
- Approximation algorithms for combinatorial problems
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- Logical definability of NP optimization problems
- Optimization, approximation, and complexity classes
This page was built for publication: A note on the descriptive complexity of maximization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685495)
