Counting solutions to CSP using generating polynomials

Constraint Satisfaction Problems (CSPs) are ubiquitous in computer science and specifically in AI. This paper presents a method of solving the counting problem for a wide class of CSPs using generating polynomials. Analysis of our method shows that it is much more efficient than the classic dynamic programming approach. For example, in the case of #SAT, our algorithm improves a result of Samer and Szeider. The presented algorithms mostly use algebraic operations on multivariate polynomials, which allows application of known optimizations and makes it possible to use existing software to implement them easily.