| RUS ENG |
| Полная версия |
|
|
|
| СЕМИНАРЫ |
|
Коллоквиум Факультета компьютерных наук НИУ ВШЭ
|
|||
|
|
|||
|
Мин-плюс многочлены и циклические игры Владимир Подольскийab a Математический институт им. В. А. Стеклова Российской академии наук b Национальный исследовательский университет "Высшая школа экономики", г. Москва |
|||
|
Аннотация: Мин-плюс (или тропическим) полукольцом называется множество рациональных чисел с двумя операциями: мин-плюс сложением, которая есть просто операция взятия минимума, и мин-плюс умножением, которое есть обычное сложение. Многочлены над мин-плюс полукольцом определяются по аналогии с классическими многочленами. По существу, мин-плюс многочлен задает кусочно-линейную функцию от своих переменных. Корнем многочлена называется точка негладкости этой функции. В этом докладе мы рассмотрим алгоритмические задачи, связанные с мин-плюс многочленами. Более конкретно, нас будет интересовать разрешимость систем линейных мин-плюс многочленов. Эта задача оказывается полиномиально эквивалентной задаче об определении победителя в так называемых циклических играх (mean payoff games), известной задаче, лежащей в пересечении сложностных классов NP и coNP. Второй результат, который планируется обсудить в ходе доклада, это аналог теоремы Гильберта о нулях для мин-плюс алгебры. Доклад основан на совместных работах с Д.Ю. Григорьевым. |
|||
