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