Solving equations over small unary algebras

Abstract

We consider the problem of solving a system of polynomial equations over fixed algebra $A$ which we call MPolSat($A$). We restrict ourselves to unary algebras and give a partial characterization of complexity of MPolSat($A$). We isolate a preorder $P(A)$ to show that when $A$ has at most 3 elements then MPolSat($A$) is in $P$ when width of $P(A)$ is at most 2 and is NP-complete otherwise. We show also that if $P ≠ NP$ then the class of unary algebras solvable in polynomial time is not closed under homomorphic images.

Keywords

• algebra
• sat
• computational complexity
• dichotomy
• [info.info-lo] computer science [cs]/logic in computer science [cs.lo]
• [info.info-sc] computer science [cs]/symbolic computation [cs.sc]