Дата публикации: 2024

Дата публикации в реестре: 2025-02-11T14:40:10Z

Аннотация:

Описан полиномиальный алгоритм, позволяющий по произвольному разрешенному относительно неизвестных уравнению вида w(xi,...,xn) = [a,b], где w(xi,...,xn) — групповое слово в алфавите неизвестных, a [a,b] — коммутатор свободных образующих а и b свободной группы F2, определить, существует ли решение этого уравнения, удовлетворяющее условию xi,... ,xn ∈ F(1)2, где F(1)2 — коммутант группы F2. Установлено существование полиномиального алгоритма, позволяющего по произвольному разрешенному относительно неизвестных уравнению вида w(xi,..., xn) = g(a, b), где g(a, b) — элемент длины меньше 4 свободной группы F2, определить, существует ли решение этого уравнения, удовлетворяющее условию xi,... , xt ∈ F(1)2, где t— произвольное фиксированное число между 1 и n. Доказана алгоритмическая разрешимость аналогичной проблемы для уравнений w(xi, a, b) = 1 с одной переменной xi.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2024. № 66. С. 5-13