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/

[1] Edmunds C. C., “On the endomorphisms problem for free group”, Comm. Algebra, 1975, no. 3, 7–20 | MR

[2] Lyndon R. C., “Dependence in groups”, Colloq. Math., 1966, no. 4, 275–283 | MR | Zbl

[3] Wicks M. J., “A general solution of binary homogeneous equations over free groups”, Pacif. J. Math., 41:2 (1972), 543–561 | MR | Zbl

[4] Schupp P. E., “On the substitution problem for free groups”, Proc. Amer. Math. Soc., 23:2 (1969), 421–423 | DOI | MR | Zbl

[5] Makanin G. S., “Uravneniya v svobodnykh gruppakh”, Izv. AN SSSR. Ser. matem., 46:6 (1982), 1199–1273 | MR | Zbl

[6] Romankov V. A., “O nerazreshimosti problemy endomorfnoi svodimosti v svobodnykh nilpotentnykh gruppakh i v svobodnykh koltsakh”, Algebra i logika, 16:4 (1977), 457–471 | MR | Zbl

[7] Repin N. N., “Nekotorye prosto zadannye gruppy, dlya kotorykh nevozmozhen algoritm, raspoznayuschii razreshimost uravnenii”, Voprosy kibernetiki. Slozhnost vychislenii i prikladnaya matematicheskaya logika, M., 1988, 167–174 | MR

[8] Shpilrain V. E., “Ob uravneniyakh v gruppakh vida $F/\gamma_n(R)$”, Algoritm. problemy grupp i polugrupp, TGPI, Tula, 1990, 164–183 | MR

[9] Papadimitriu Kh., Staiglits K., Kombinatornaya optimizatsiya. Algoritmy i slozhnost, Mir, M., 1985

[10] Krouell R., Foks R., Vvedenie v teoriyu uzlov, Mir, M., 1967

[11] Cohen D., Groups of cohomological dimension one, Lecture Notes in Math., 245, Springer-Verlag, Berlin–New York, 1972 | Zbl

[12] Maltsev A. I., “Ob uravnenii $zxyx^{-1}y^{-1}z^{-1}=aba^{-1}b^{-1}$ v svobodnoi gruppe”, Algebra i logika, 1:5 (1962), 45–50 | MR | Zbl

[13] Zieschang H., “Üder Automorphismen ebener diskontinuerlicher Gruppen”, Math. Ann., 166 (1966), 148–167 | DOI | MR | Zbl

[14] Bavard C., “Longueur stable des commutateurs”, L'Enseignment Mathematique, 37 (1991), 109–150 | MR | Zbl

[15] Lyndon R. C., Schützenberger M. P., “The equation $a^M=b^Nc^P$ in a free group”, Mich. Math. J., 1962, no. 9, 289–298 | MR | Zbl

[16] Baumslag G., “On a problem of Lyndon”, J. London Math. Soc., 1960, no. 35, 30–32 | DOI | MR | Zbl

[17] Schenkman E., “The equation $a^nb^n=c^n$ in a free group”, Ann. Math., 70 (1959), 562–564 | DOI | MR | Zbl

[18] Makanin G. S., “Razreshimost universalnoi i pozitivnoi teorii svobodnoi gruppy”, Izv. AN SSSR. Ser. matem., 48:4 (1984), 735–749 | MR | Zbl

[19] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | Zbl