On the solvability problem for equations with a~single coefficient

V. G. Durnev

Matematičeskie zametki, Tome 59 (1996) no. 6, pp. 832-845

Résumé

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.