Solving equations over small unary algebras - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

Solving equations over small unary algebras

Résumé

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.
Fichier principal
Vignette du fichier
dmAF0103.pdf (181.7 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01183338 , version 1 (12-08-2015)

Identifiants

Citer

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⟩
27 Consultations
486 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More