Przemyslaw Broniek
-
Solving equations over small unary algebras
dmtcs:3474 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
-
https://doi.org/10.46298/dmtcs.3474
Solving equations over small unary algebrasConference paper
Authors: Przemyslaw Broniek 1,2
NULL
Przemyslaw Broniek
1 Uniwersytet Jagielloński w Krakowie = Jagiellonian University
2 Uniwersytet Jagielloński w Krakowie = Jagiellonian University = Université Jagellon de Cracovie
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.