Counting Problems and Clones of Functions
Andrei A. Bulatov and Amir Hedayaty
Counting solutions of various combinatorial problems is a well established and intensively studied area of theoretical computer science. Its applications range from networking to statistical physics. The central question in this area is, of course, the complexity of and algorithms for problems of this type. It turns out that in many important cases these questions can be answered with aid of clones of functions of multi-valued logic. In this paper we give a short review of the connections between the two areas and related results; then we extend those connections to approximate counting and present some initial results showing that clones of functions are useful in this area as well.
Keywords: complexity, algorithms, counting problems, CSP, clones