2012/04/20 by Dima Grigoriev, Grigoriev, Dima, Vladimir V. Podolskii +1
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algebraic Geometry (math.AG) #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #cs.CC #math.AG
paper · pdf · doi:10.48550/arxiv.1204.4578
36 pages
arxiv created 2012/04/20 · openalex publication_date 2012/04/20 · arxiv updated 2012/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A tropical (or min-plus) semiring is a set ℤ (or \mathbbZ ∪ \∞\) endowed with two operations: ⊕, which is just usual minimum, and \odot, which is usual addition. In tropical algebra the vector x is a solution to a polynomial g1(x) ⊕ g2(x) ⊕...⊕ gk(x), where gi(x)'s are tropical monomials, if the minimum in mini(gi(x)) is attained at least twice. In min-plus algebra solutions of systems of equations of the form g1(x)⊕...⊕ gk(x) = h1(x)⊕...⊕ hl(x) are studied. In this paper we consider computational problems related to tropical linear system. We show that the solvability problem (both over ℤ and ℤ ∪ \∞\) and the problem of deciding the equivalence of two linear systems (both over ℤ and ℤ ∪ \∞\) are equivalent under polynomial-time reduction 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 are NP-complete. We also extend some of our results to the systems of min-plus linear inequalities.