(1) Uniwersytet Jagielloński w Krakowie = Jagiellonian University
(2) Uniwersytet Jagielloński w Krakowie = Jagiellonian University = Université Jagellon de Cracovie
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
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
