A tropical (or min-plus) semiring is a set natural numers, possibly with infinity, endowed with two operations: tropical addition, which is just usual minimum operation, and tropical multiplication, which is usual addition. In tropical algebra a vector x is a solution to a polynomial min(g_1(x), g_2(x),...,g_k(x)), where g_i(x)'s are tropical monomials, if the minimum is attained at least twice. In min-plus algebra solutions of systems of equations of the form min(g_1(x),...,g_k(x)) = min(h_1(x),..., 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 integers and over integers with infinity) and the problem of deciding the equivalence of two linear systems (both over integers and over integers with infinity) are equivalent under polynomial-time reductions to mean payoff games and are also equivalent to analogous problems in min-plus algebra. 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 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. http://arxiv.org/abs/1204.4578