Counting solutions of equations over two-element algebras

Abstract

Solving equations is one of the most important problems in computer science. Apart from the problem of existence of solutions of equations we may consider the problem of a number of solutions of equations. Such a problem is much more difficult than the decision one. This paper presents a complete classification of the complexity of the problem of counting solutions of equations over any fixed two-element algebra. It is shown that the complexity of such problems depends only on the clone of term operations of the algebra and for any fixed two-element algebra such a problem is either in FP or #Pcomplete.