Shitov, Yaroslav Nikolaevich Tropical semimodules of dimension two. (English) Zbl 1316.15032 St. Petersbg. Math. J. 26, No. 2, 341-350 (2015) and Algebra Anal. 26, No. 2, 216-228 (2014). Summary: The tropical arithmetic operations on \( \mathbb{R}\) are defined as \( a\oplus b=\min \{a,b\}\) and \( a\otimes b=a+b\). In the paper, the concept of a semimodule is discussed, which is rather ill-behaved in tropical mathematics. The semimodules \( S\subset \mathbb{R}^n\) having topological dimension two are studied and it is shown that any such \( S\) has a finite weak dimension not exceeding \( n\). For a fixed \( k\), a polynomial time algorithm is constructed that decides whether \( S\) is contained in some tropical semimodule of weak dimension \( k\) or not. This result provides a solution of a problem that has been open for eight years. Cited in 2 Documents MSC: 15A80 Max-plus and related algebras 16D80 Other classes of modules and ideals in associative algebras 65Y20 Complexity and performance of numerical algorithms Keywords:tropical mathematics; linear algebra; computational complexity; semimodules; polynomial time algorithm PDFBibTeX XMLCite \textit{Y. N. Shitov}, St. Petersbg. Math. J. 26, No. 2, 341--350 (2015; Zbl 1316.15032) Full Text: DOI References: [1] [AGG] M. Akian, S. Gaubert, and A. Guterman, Linear independence over tropical semirings and beyond, Contemp. Math., vol. 495, Amer. Math. Soc., Providence, RI, 2009, pp. 1-38. · Zbl 1182.15002 [2] [BCOQ] F. Baccelli, G. Cohen, G. J. Olsder, and J. P. Quadrat, Synchronization and Linearity, An algebra for discrete event systems, John Wiley & Sons, Ltd., Chichester, 1992. · Zbl 0824.93003 [3] [Barv2] A. I. Barvinok, Two algorithmic results for the traveling salesman problem, Math. Oper. Res. 21 (1996), no. 1, 65-84. · Zbl 0846.90115 [4] [Dev1] M. Develin, The moduli space of \(n\) tropically collinear points in \(\mathbb R^d\), Collect. Math. 56 (2005), no. 1, 1-19. · Zbl 1069.52014 [5] [DS] M. Develin and B. Sturmfels, Tropical convexity, Doc. Math. 9 (2004), 1-27. (electronic) · Zbl 1054.52004 [6] [DSS] M. Develin, F. Santos, and B. Sturmfels, On the rank of a tropical matrix, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 213-242. · Zbl 1095.15001 [7] [EML] M. Einsiedler, M. Kapranov, and D. Lind, Non-Archimedean amoebas and tropical varieties, J. Reine Angew. Math. 601 (2006), 139-157. · Zbl 1115.14051 [8] [FR] J. Ferrante and C. Rackoff, A decision procedure for the first order theory of real addition with order, SIAM J. Comput. 4 (1975), 69-76. · Zbl 0294.02022 [9] [Gau] S. Gaubert, Methods and applications of \((\max,+)\) linear algebra, STACS 97 (Lubek), Lecture Notes in Comput. Sci., vol. 1200, Springer, Berlin, 1997, pp. 261-282. · Zbl 1498.15034 [10] [Golan] J. S. Golan, Semirings and their applications, Kluwer Acad. Publ., Dordrecht, 1999. · Zbl 0947.16034 [11] [Mas2] G. Litvinov and V. Maslov, The correspondence principle for idempotent calculus and some computer applications, Cambridge Univ. Press, Cambridge, 1998, pp. 420-443. · Zbl 0897.68050 [12] [myTMF] Ya. Shitov, The complexity of tropical matrix factorization, Adv. in Math. 254 (2014), 138-156. · Zbl 1359.68112 [13] [Viro] O. Viro, Dequantization of real algebraic geometry on logarithmic paper, European Congress of Math., Vol. 1, Progr. Math., vol. 201, Birkh\"auser, Basel, 2001, pp. 135-146. · Zbl 1024.14026 [14] [Wag] E. Wagneur, Moduloids and pseudomodules. I, Dimension theory, Discrete Math. 98 (1991), no. 1, 57-73. · Zbl 0757.06008 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.