RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
15 октября 2013 г. 18:30–20:05, г. Москва, ГЗ МГУ, ауд. 16-04
 


$\mathit{NP}$-полнота одного класса квадратичных уравнений в свободных метабелевых группах

И. Г. Лысёнок

Количество просмотров:
Эта страница:89

Аннотация: В докладе будут рассмотрены уравнения вида
$$ c_0   x_1^{-1} c_1 x_1   x_2^{-1} c_2 x_2 …x_m^{-1} c_m x_m = 1 $$
в свободной метабелевой группе $M_n$ ранга $n \ge 2$. Частными случаями проблемы распознавания разрешимости таких уравнений являются проблемы распознавания равенства и сопряженности слов в группе $M_n$. В докладе будет рассказано о совместной работе докладчика и А.Ушакова, в которой доказана $\mathit{NP}$-полнота проблемы распознавания разрешимости уравнений указанного вида.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019