Complexity of Tropical and Min-plus Linear Prevarieties

• Published in: Computational complexity 2015-03, Vol.24 (1), p.31-64
• Main Authors: Grigoriev, Dima, Podolskii, Vladimir V.
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Computational Mathematics and Numerical Analysis; Computer Science; Mathematics
• ISSN: 1016-3328; 1420-8954
• DOI: 10.1007/s00037-013-0077-5

A tropical (or min-plus) semiring is a set Z (or Z ∪ { ∞ } ) endowed with two operations: ⊕ , which is just usual minimum, and ⊙ , which is usual addition. In tropical algebra, a vector x is a solution to a polynomial g 1 ( x ) ⊕ g 2 ( x ) ⊕ ⋯ ⊕ g k ( x ) , where the 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 ) ⊕ ⋯ ⊕ g k ( x ) = h 1 ( x ) ⊕ ⋯ ⊕ h l ( x ) are studied. In this paper, we consider computational problems related to tropical linear system. We show that the solvability problem (both over Z and Z ∪ { ∞ } ) and the problem of deciding the equivalence of two linear systems (both over Z and Z ∪ { ∞ } ) 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 NP ∩ 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 NP -complete.