Видеотека: И. Г. Лысeнок, Уравнения в группах и некоторые задачи геометрической комбинаторики

ВИДЕОТЕКА


Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая логика» 25 декабря 2018 г. 12:05, г. Москва, МИАН, ул. Губкина, д. 8, конференц-зал, 9 этаж

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