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

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






«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
7 апреля 2015 г. 18:30–20:05, г. Москва, Математический институт им.В.А.Стеклова РАН
 


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

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

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

Аннотация: Действительнозначная функция $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
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021