Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

  • 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 PNP 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 245 times.
This article's PDF has been downloaded 241 times.