RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 1996 Volume 59, Issue 6, Pages 832–845 (Mi mzm1782)

This article is cited in 10 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.

UDC: 519.71+519.4+512

Received: 30.06.1994

DOI: 10.4213/mzm1782


 English version:
Mathematical Notes, 1996, 59:6, 601–610

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025