В этом докладе рассматриваются алгоритмические задачи, связанные с мин-плюс многочленами. Конкретнее — разрешимость систем линейных мин-плюс многочленов. Эта задача оказывается полиномиально эквивалентной задаче об определении победителя в так называемых циклических играх (mean payoff games), известной задаче, лежащей в пересечении сложностных классов NP и coNP. Второй результат, который обсуждается в ходе доклада, это аналог [теоремы Гильберта о нулях][1] для мин-плюс алгебры.




Мин-плюс (или тропическим) полукольцом называется множество рациональных чисел с двумя операциями: мин-плюс сложением, которая есть просто операция взятия минимума, и мин-плюс умножением, которое есть обычное сложение. Многочлены над мин-плюс полукольцом определяются по аналогии с классическими многочленами. По существу, мин-плюс многочлен задает кусочно-линейную функцию от своих переменных. Корнем многочлена называется точка негладкости этой функции. Доклад был прочитан на факультете компьютерных наук, открытом в НИУ ВШЭ при поддержке Яндекса. Лектор Владимир Подольский — старший научный сотрудник Математического института им. В.А. Стеклова. На ФКН читает лекции и ведет семинары в рамках [курса «Дискретная математика».][2] Доклад основан на совместных работах с [Дмитрием Григорьевым][3]. Под катом — полная расшифровка лекции. [Читать дальше →][4]

[1]: https://ru.wikipedia.org/wiki/Теорема_Гильберта_о_нулях
[2]: http://www.hse.ru/edu/courses/152257349.html
[3]: https://en.wikipedia.org/wiki/Dima_Grigoriev
[4]: http://habrahabr.ru/post/264409/#habracut