01/01/1992 09:00 AM
Computer Science
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 obtained in this way 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. These results set the foundation for further study of the descriptive complexity of the class #P. In contrast, we show, under reasonable complexity theoretic assumptions, that it is an undecidable problem to tell if a counting problem expressed in our framework is polynomial time computable or is approximable by a randomized polynomial time algorithm. Finally, we discuss some open problems which arise naturally from this work.
