|
This article is cited in 9 scientific papers (total in 9 papers)
On the solvability problem for equations with a single coefficient
V. G. Durnev P. G. Demidov Yaroslavl State University
Abstract:
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.
Received: 30.06.1994
Citation:
V. G. Durnev, “On the solvability problem for equations with a single coefficient”, Mat. Zametki, 59:6 (1996), 832–845; Math. Notes, 59:6 (1996), 601–610
Linking options:
https://www.mathnet.ru/eng/mzm1782https://doi.org/10.4213/mzm1782 https://www.mathnet.ru/eng/mzm/v59/i6/p832
|
|