04/01/1991 09:00 AM
Computer Engineering
In this paper we introduce a new approach to the logical definability of NP optimization problems by focusing on the expressibility of feasible solutions. We show that in this framework first-order sentences capture exactly all polynomially bounded optimization problems. We also show that, assuming P not= NP, it is an undecidable problem to tell if a given first-order sentence defines an approximable optimization problem. We then isolate a syntactically defined class of NP minimization problems that contains the MIN SET COVER problem and has the property that every problem in it has a logarithmic approximation algorithm. We conclude by giving a machine-independent characterization of the NP =? co-NP problem in terms of logical expressibility of the MAX CLIQUE problem.
