Complexity of tropical and min-plus linear prevarieties

Abstract: A tropical (or min-plus) semiring is a set $\mathbb{Z}$ or $\mathbb{Z \cup \{\infty\}}$
endowed with two operations: $\oplus$, which is just usual minimum operation, and $\odot$, which is usual addition.
In tropical algebra a vector $x$ is a solution to a polynomial $g_1(x) \oplus g_2(x) \oplus \ldots \oplus g_k(x)$,
where $g_i(x)$'s are tropical monomials, if the minimum in $\min_i(g_{i}(x))$ is attained at least twice.
In min-plus algebra solutions of systems of equations of the form $g_1(x)\oplus \ldots \oplus g_k(x) = h_1(x)\oplus \ldots \oplus h_l(x)$
are studied.

In this talk we are going to consider computational problems related to tropical linear system.
We show that the solvability problem (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$)
and the problem of deciding the equivalence of two linear systems
(both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$) are equivalent under polynomial-time reductions to mean payoff games
and are also equivalent to analogous problems in min-plus algebra.
%In particular, all these problems belong to $\mathsf{NP} \cap \mathsf{coNP}$.
Thus, we provide a tight connection of computational aspects of tropical linear algebra with mean payoff games and min-plus linear algebra.
On the other hand we show that computing the dimension of the solution space of a
tropical linear system and of a min-plus linear system is $\mathsf{NP}$-complete.

For systems of tropical and min-plus polynomials of higher degree we prove an analog of Nullstellensatz theorem.

Our analysis also yields a structural connection between systems of tropical polynomials and systems of min-plus polynomials.
Previously tropical and min-plus branches of algebra over min-plus semiring were studied in parallel.

The talk is based on the joint work with Dima Grigoriev.