DMTCS Proceedings, Computational Logic and Applications, CLA '05

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional