Solving equations over small unary algebras
Przemyslaw Broniek
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.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page