Skip to main content
Technical Reports
Navigation
Technical Reports
UCSC-CRL-90-48: LOGICAL DEFINABILITY OF NP OPTIMIZATION PROBLEMS
« Previous
Next »
Authors
Published On
09/01/1990 09:00 AM
Department
Computer Engineering
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.
Download
UCSC-CRL-90-48
Error | Technical Reports
Technical Reports
Error
The website encountered an unexpected error. Please try again later.