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

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





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








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


Эффективный алгоритм для решения проблемы распознавания равенства в пространстве классов квазиморфизмов свободной группы

А. Л. Таламбуца

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

Аннотация: Действительнозначная функция $f$, определенная на данной группе $G$, называется квазиморфизмом этой группы, если существует такая константа $C\ge 0$, что для любых $x,y\in G$ выполнено неравенство $|f(xy)-f(x)-f(y)|<C$. Квазиморфизмы $f,g$ данной группы считаются элементами одного класса, если функция $|f-g|$ ограничена некоторой константой на всей группе $G$.
В 1980 году Р.Брукс построил бесконечномерное подпространство в линейном пространстве всех классов квазиморфизмов свободной группы. Известно, что классы Брукса являются линейно зависимыми, и в работе Калегари -Уолкера 2011 года был предложен экспоненциальный по времени алгоритм, который проверяет равенство нулю линейной суммы классов.
В докладе будет описан алгоритм, который решает данную задачу за линейное время в случае, когда сумма дана с целыми коэффициентами и за квадратичное время, если коэффициенты рациональные.

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