12/01/1992 09:00 AM
Computer Science
This thesis is about the descriptive complexity of two function classes, namely, NP optimization problems and #P counting problems. It is divided into two parts. In Part I we investigate 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. Next, we analyze the relative expressive power of various classes of optimization problems in this framework. We introduce an alternate approach to the logical definability of NP optimization problems by focusing on the expressibility of feasible solutions. We study the relationships between classes defined in these two frameworks. We identify sufficient syntactic conditions for approximability and isolate rich classes of approximate problems. 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. Regarding the relationship between approximability and logical definability, we show that, assuming P /= NP, it is undecidable to tell if a given first-order sentence defines an approximable optimization problem. Finally, we provide a machine-independent characterization of the NP ?= co-NP problem in terms of logical expressibility of the MAX CLIQUE problem. We conclude Part I by discussing some future directions in this line of research. In Part II, we give a logic based framework for defining counting problems and show that it exactly captures the problems in Valiant\'s counting class #P. We study the expressive power of the framework under natural syntactic restrictions and show that some of the subclasses so obtained contain problems in #P with interesting computational properties. In particular, using syntactic conditions, we isolate a class of polynomial time computable #P problems, and also a class in which every problem is approximable by a polynomial time randomized algorithm. We show, under reasonable complexity theoretic assumptions, that it is undecidable to tell if a counting problem expressed in our framework is polynomial time computable or is approximable by a randomized polynomial time algorithm. This work sets the foundation for further study of the descriptive complexity of the class #P. Notes: Ph.D. Thesis
