On the solvability problem for equations with a single coefficient

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 formw(x ₁, ...,x _n)=g, whereg is a coefficient, i.e., an element of the group, andw(x ₁, ...,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 formw(x ₁,...,x _n)=g, wherew(x ₁,...,x _n) is a semigroup word in the alphabet of unknowns andg is an element of a free semigroup. Translated fromMatematicheskie Zametki, Vol. 59, No. 6, pp. 832–845, June, 1996. I wish to express my deep gratitude to S. I. Adyan and A. A. Razborov for the discussion of the present paper and for valuable remarks concerning the exposition. This research was partially supported by the International Science Foundation under grant MUV000.