DOAJ Open Access 2005

Solving equations over small unary algebras

Przemyslaw Broniek

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (1)

Przemyslaw Broniek

Format Sitasi

APA MLA BibTeX

Broniek, P. (2005). Solving equations over small unary algebras. https://doi.org/10.46298/dmtcs.3474

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.3474

Informasi Jurnal

Tahun Terbit: 2005
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.3474
Akses: Open Access ✓