Min-Plus polynomials and mean payoff games

The Min-Plus semiring, or tropical semiring, is the set of rationals with two operations: "min-plus addition," which simply corresponds to the minimum of two arguments, and "min-plus multiplication," which is the usual addition. Polynomials over the min-plus semiring are defined in a similar way to classical polynomials and are essentially piecewise linear functions of their arguments. Roots of these polynomials are defined to be points where the function is nonsmooth.
In this talk we consider algorithmic problems associated to min-plus polynomials. More specifically, we will be interested in solvability of systems of linear min-plus polynomials. This problem turns out to be polynomially equivalent to the problem of determining the winner in mean payoff games, a problem known to belong to the intersection of NP and coNP complexity classes.
The second result that we plan to discuss in the talk is the min-plus algebraic analogue of Hilbert's Nullstellensatz.
The talk is based on joint work with Dmitry Grigoriev.