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, 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 \cdots \oplus 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)\oplus \cdots \oplus g_k(x) = h_1(x)\oplus \cdots \oplus 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 \({\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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Marianne Akian, Stephane Gaubert & Alexander Guterman (2012). Tropical polyhedra are equivalent to mean payoff games. International Journal of Algebra and Computation 22(1), 43pp.
Xavier Allamigeon, Stephane Gaubert & Ricardo D. Katz (2011). Tropical polar cones, hypergraph transversals, and mean payoff games. LINEAR ALGEBRA AND ITS APPLICATIONS 435, 1549–1574. URL doi:10.1016/j.laa.2011.02.004.
Sanjeev Arora & Boaz Barak (2009). Computational Complexity - A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4, I-XXIV, 1-579 .
Marc Bezem, Robert Nieuwenhuis & Enric Rodríguez-Carbonell (2010). Hard problems in max-algebra, control theory, hypergraphs and other areas. Inf. Process. Lett. 110(4), 133–138.
Peter Butkovič (2010). Max-linear Systems: Theory and Algorithms. Springer.
Alex Davydow (2012). Upper and lower bounds for Grigoriev’s algorithm for solving integral tropical linear systems. Combinatorics and graph theory. Part IV, RuFiDiM’11, Zap. Nauchn. Sem. POMI, POMI, St. Petersburg 402, 69–82.
Alex Davydow (2013). New Algorithms for Solving Tropical Linear Systems. CoRR abs/1309.5206.
Mike Develin, Francisco Santos & Bernd Sturmfels (2005). On the rank of a tropical matrix. Combinatorial and Computational Geometry 52, 213–242.
Michael R. Garey & David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1044-7.
Dima Grigoriev (2013) Complexity of Solving Tropical Linear Systems. Computational Complexity 22(1): 71–88
Dima Grigoriev & Vladimir V. Podolskii (2012). Complexity of tropical and min-plus linear prevarieties. CoRR abs/1204.4578.
Ilia Itenberg, Grigory Mikhalkin & Eugenii I. Shustin (2007). Tropical Algebraic Geometry. Oberwolfach seminars, Birkhäuser.
Ki Hang Kim & Fred W. Roush (2005). Factorization of polynomials in one variable over the tropical semiring. CoRR abs/0501167v2.
Ki Hang Kim, Fred W. Roush (2006) Kapranov rank vs. tropical rank. Proc. Amer. Math. Soc 134: 2487–2494
Hartmut Klauck (2002). Algorithms for Parity Games. In Automata Logics, and Infinite Games, Erich Grädel, Wolfgang Thomas & Thomas Wilke, editors, volume 2500 of Lecture Notes in Computer Science, 553–563. Springer Berlin / Heidelberg. ISBN 978-3-540-00388-5.
Rolf H. Möhring, Martin Skutella & Frederik Stork (2004). Scheduling with AND/OR Precedence Constraints. SIAM J. Comput. 33(2), 393–415.
Jürgen Richter-Gebert, Bernd Sturmfels, Thorsten Theobald (2003) First steps in tropical geometry. Idempotent Mathematics and Mathematical Physics, . Contemporary Mathematics 377: 289–317
Bernd Sturmfels (2002). Solving Systems of Polynomial Equations, volume 97 of CBMS Regional Conference in Math. American Mathematical Society.
Thorsten Theobald (2006) On the frontiers of polynomial computations in tropical geometry. J. Symb. Comput. 41(12): 1360–1375
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grigoriev, D., Podolskii, V.V. Complexity of Tropical and Min-plus Linear Prevarieties. comput. complex. 24, 31–64 (2015). https://doi.org/10.1007/s00037-013-0077-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-013-0077-5
Keywords
- Tropical linear systems
- min-plus linear systems
- tropical prevarieties
- min-plus prevarieties
- mean payoff games