Complexity of tropical and MIN-plus linear prevarieties (Q2353186)

This paper studies the complexity of computational problems for linear systems in tropical and min-plus algebras and, more generally, the interrelation between these two algebras. Both the solvability and the linear systems equivalence problems in tropical algebras are shown to be equivalent to mean pay off games, and likewise for the analogue problems in min-plus algebras. Moreover, computing the dimension of the solution space of a tropical linear system or of a min-plus linear system is found to be NP-complete. The techniques for the proofs are mostly combinatorial.