Эта публикация цитируется в
2 статьях
Об уравнениях в свободных группах, разрешенных относительно неизвестных, с ограничениями на решения
В. Г. Дурнев,
О. В. Зеткина Ярославский государственный университет им. П. Г. Демидова
Аннотация:
Устанавливается алгоритмическая неразрешимость проблемы разрешимости в свободной группе
$F_2$ ранга 2 со свободными образующими
$a$ и
$b$ для систем уравнений с ограничениями на решения вида
$$
w(x_1, \dots , x_n) = [a, b] \& \overset{t}{\underset{i=1}{\&}} x_i \in F_2^{(1)}
$$
и вида
$$
w(x_1, \dots , x_n) = [a, b] \& x_1 \in F_2^{(2)},
$$
где
$w(x_1, \dots , x_n)$ – слово в алфавите неизвестных
$\{x_1, \dots , x_n\}$,
$[a, b]$ – коммутатор свободных образующих
$a$ и
$b$,
$F_2^{(1)}$ – коммутант группы
$F_2$, а
$F_2^{(2)}$ – ее второй коммутант.
Устанавливается существование полиномиального алгоритма, позволяющего по произвольному разрешенному относительно неизвестных уравнению вида
$$
w(x_{1},\dots ,x_{n} ) = g(a, b),
$$
где
$w(x_{1},\dots ,x_{n} )$ – групповое слово в алфавите неизвестных, а
$g(a, b)$ – элемент длины меньше 4 свободной группы
$F_{2}$, определить, существует ли решение этого уравнения, удовлетворяющее условию
$$
x_{1} \in F_{2}^{(s)},\dots ,x_{t} \in F_{2}^{(s)},
$$
где
$t$ – произвольное фиксированное число между 1 и
$n$, а
$F_2^{(s)}$ –
$s$-ый коммутант группы
$F_2$.
Устанавливается алгоритмическая разрешимость аналогичных проблем для уравнений с одним неизвестным.
УДК:
510.53+
512.54.0+
512.54.03+
512.54.05+512.543.72
Поступила в редакцию: 18.05.2012