В докладе будет рассказано о сведении некоторых специальных случаев уравнений в группах к
естественных задачам геометрической комбинаторики.
Мы рассмотрим уравнения вида
$$
x_1 c_1 x_1^{-1} \dots x_n c_n x_n^{-1} = 1
$$
(где $x_i$ — неизвестные, а $c_i$ — коэффициенты) в свободных и свободных метабелевых группах.
В обоих случаях сведение позволяет установить NP-полноту задачи о разрешимости уравнений из рассматриваемого класса.
Обратная связь: