Уравнения в группах и некоторые задачи геометрической комбинаторики

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