Counting solutions of equations over two-element algebras
Jacek Krzaczkowski · Studia Iuridica Lublinensia (Uniwersytet Marii Curie-Skłodowskiej w Lublinie) · 2006
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.