page 1  (30 pages)
2to next section

Logical Definability of

NP Optimization Problems?

Phokion G. Kolaitis Madhukar N. Thakury

UCSC-CRL-93-10z

Computer and Information Sciences

University of California Santa Cruz

Santa Cruz, CA 95064

Abstract: We investigate here NP optimization problems from a logical definability standpoint. We show that the class of optimization problems whose optimum is definable using first-order formulae coincides with the class of polynomially bounded NP optimization problems on finite structures. After this, we analyze the relative expressive power of various classes of optimization problems that arise in this framework. Some of our results show that logical definability has different implications for NP maximization problems than it has for NP minimization problems, in terms of both expressive power and approximation properties.

?To appear in Information and Computation. Research partially supported by NSF Grants CCR- 8905038 and CCR-9108631.
ye-mail addresses: kolaitis@cse.ucsc.edu, thakur@cse.ucsc.edu
zsupersedes Technical report UCSC-CRL-90-48