RUS  ENG
Полная версия
ЖУРНАЛЫ // Чебышевский сборник // Архив

Чебышевский сб., 2012, том 13, выпуск 1, страницы 63–80 (Mi cheb15)

Эта публикация цитируется в 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



© МИАН, 2024