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

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





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








Коллоквиум Факультета компьютерных наук НИУ ВШЭ
30 апреля 2015 г. 16:40–18:00, г. Москва, Кочновский проезд, д. 3, ауд. 205
 


Мин-плюс многочлены и циклические игры

В. В. Подольскийab

a Математический институт им. В. А. Стеклова Российской академии наук
b Национальный исследовательский университет "Высшая школа экономики", г. Москва

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





Аннотация: Мин-плюс (или тропическим) полукольцом называется множество рациональных чисел с двумя операциями: мин-плюс сложением, которая есть просто операция взятия минимума, и мин-плюс умножением, которое есть обычное сложение. Многочлены над мин-плюс полукольцом определяются по аналогии с классическими многочленами. По существу, мин-плюс многочлен задает кусочно-линейную функцию от своих переменных. Корнем многочлена называется точка негладкости этой функции.
В этом докладе мы рассмотрим алгоритмические задачи, связанные с мин-плюс многочленами. Более конкретно, нас будет интересовать разрешимость систем линейных мин-плюс многочленов. Эта задача оказывается полиномиально эквивалентной задаче об определении победителя в так называемых циклических играх (mean payoff games), известной задаче, лежащей в пересечении сложностных классов NP и coNP.
Второй результат, который планируется обсудить в ходе доклада, это аналог теоремы Гильберта о нулях для мин-плюс алгебры.
Доклад основан на совместных работах с Д.Ю. Григорьевым.

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