К проблеме разрешимости уравнений с одним коэффициентом

Доказывается, что общая проблема разрешимости уравнений в свободной группе полиномиально сводима к проблеме разрешимости уравнений вида $w(x_1,\dots,x_n)=g$, где $g$ – коэффициент, т.е. элемент группы, а $w(x_1,\dots,x_n)$ – групповое слово в алфавите неизвестных. Устанавливается NP-полнота проблемы разрешимости в свободной полугруппе уравнений вида $w(x_1,\dots,x_n)=g$, где $w(x_1,\dots,x_n)$ – полугрупповое слово в алфавите неизвестных, а $g$ – элемент свободной полугруппы.
Библиография: 19 названий.