Об уравнениях в алгебраической системе $(\mathbb Z,\min, +)$

В докладе будет рассматриваться так называемое мин-плюс полукольцо $(\mathbb Z,\oplus,\otimes)$, где $x \oplus y = \min(x,y)$ и $x \otimes y = x+y$. Мы будем рассматривать уравнения двух типов над этим полукольцом: односторонние и двухсторонние линейные мин-плюс уравнения. Односторонним линейным мин-плюс уравнением мы в рамках этого доклада будем называть выражение вида $(a_1 \otimes x_1) \oplus \ldots \oplus (a_n \otimes x_n)$. Вектор $(x_1, \ldots, x_n)$ является решением такого уравнения, если минимум $\min_i(a_i + x_i)$ достигается дважды. Двухсторонние линейные мин-плюс уравнения – это уравнения вида $(a_1 \otimes x_1) \oplus \ldots \oplus (a_n \otimes x_n) = (b_1 \otimes x_1) \oplus \ldots \oplus (b_n \otimes x_n)$.
В докладе мы рассматриваем алгоритмические вопросы связанные с системами двухсторонних и односторонних линейных мин-плюс уравнений. В частности, показано, что проблема распознавания разрешимости односторонних систем мин-плюс уравнений эквивалентна задаче об определении победителя в циклических играх – известной задаче из $\mathrm{NP} \cap \mathrm{coNP}$ (для двухсторонних систем аналогичный результат был известен ранее). Кроме того, доказано, что задача распознавания равносильности двух данных систем также эквивалентна задаче о циклических играх, а значит также лежит в $\mathrm{NP} \cap \mathrm{coNP}$. Этот результат доказан как для односторонних, так и для двухсторонних систем. Также доказано, что задача вычисления размерности пространства решений линейной мин-плюс системы (вновь, как односторонней, так и двухсторонней) $\mathrm{NP}$-полна.
Доклад основан на совместной работе с Д. Ю. Григорьевым.