https://hal.inria.fr/hal-01183338Broniek, PrzemyslawPrzemyslawBroniekUJ - Uniwersytet Jagielloński w Krakowie = Jagiellonian UniversitySolving equations over small unary algebrasHAL CCSD2005algebraSATcomputational complexitydichotomy[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO][INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]Episciences Iam, CoordinationDavid, René and Gardy, Danièle and Lescanne, Pierre and Zaionc, Marek2015-08-12 10:19:192021-12-07 15:33:142015-08-13 09:33:26enConference papershttps://hal.inria.fr/hal-01183338/document10.46298/dmtcs.3474application/pdf1We 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.