Geodesic
On the solvability problem for equations with a~single coefficient
Matematičeskie zametki, Tome 59 (1996) no. 6, pp. 832-845

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that the general solvability problem for equations in a free group is polynomially reducible to the solvability problem for equations of the form $w(x_1,\dots,x_n)=g$, where $g$ is a coefficient, i.e., an element of the group, and $w(x_1,\dots,x_n)$ is a group word in the alphabet of unknowns. We prove the NP-completeness of the solvability problem in a free semigroup for equations of the form $w(x_1,\dots,x_n)=g$, where $w(x_1,\dots,x_n)$ is a semigroup word in the alphabet of unknowns and $g$ is an element of a free semigroup. 
@article{MZM_1996_59_6_a3,
     author = {V. G. Durnev},
     title = {On the solvability problem for equations with a~single coefficient},
     journal = {Matemati\v{c}eskie zametki},
     pages = {832--845},
     publisher = {mathdoc},
     volume = {59},
     number = {6},
     year = {1996},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1996_59_6_a3/}
}
TY  - JOUR
AU  - V. G. Durnev
TI  - On the solvability problem for equations with a~single coefficient
JO  - Matematičeskie zametki
PY  - 1996
SP  - 832
EP  - 845
VL  - 59
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_1996_59_6_a3/
LA  - ru
ID  - MZM_1996_59_6_a3
ER  - 
%0 Journal Article
%A V. G. Durnev
%T On the solvability problem for equations with a~single coefficient
%J Matematičeskie zametki
%D 1996
%P 832-845
%V 59
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1996_59_6_a3/
%G ru
%F MZM_1996_59_6_a3
V. G. Durnev. On the solvability problem for equations with a~single coefficient. Matematičeskie zametki, Tome 59 (1996) no. 6, pp. 832-845. http://geodesic.mathdoc.fr/item/MZM_1996_59_6_a3/