Descriptive complexity of #P functions

A logic-based framework for defining counting problems is given, and it is shown that it exactly captures the problems in Valiant´s counting class #P. The expressive power of the framework is studied under natural syntactic restrictions, and it is shown that some of the subclasses obtained in this way contain problems in #P with interesting computational properties. In particular, using syntactic conditions, a class of polynomial-time-computable #P problems is isolated, as well as 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, it is shown, under reasonable complexity theoretic assumptions, that it is an undecidable problem to tell if a counting problem expressed in the framework is polynomial-time computable or is approximable by a randomized polynomial-time algorithm. Some open problems are discussed