Skip to Main content Skip to Navigation
Conference papers

Solving equations over small unary algebras

Abstract : 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.
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/hal-01183338
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 10:19:19 AM
Last modification on : Tuesday, December 7, 2021 - 3:33:14 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:35:50 AM

File

dmAF0103.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Przemyslaw Broniek. Solving equations over small unary algebras. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. pp.49-60, ⟨10.46298/dmtcs.3474⟩. ⟨hal-01183338⟩

Share

Metrics

Record views

18

Files downloads

351