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 algebrasArticle

Authors: Przemyslaw Broniek 1

  • 1 Uniwersytet Jagielloński w Krakowie = Jagiellonian University

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.


Volume: DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: algebra,SAT,computational complexity,dichotomy,[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO],[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]

1 Document citing this article

Consultation statistics

This page has been seen 147 times.
This article's PDF has been downloaded 150 times.