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 <>
Submitted on : Wednesday, August 12, 2015 - 10:19:19 AM
Last modification on : Wednesday, May 10, 2017 - 5:40:19 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:35:50 AM

File

dmAF0103.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01183338, version 1

Collections

Citation

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

Share

Metrics

Record views

64

Files downloads

526