Complexity of deciding whether a tropical linear prevariety is a tropical variety.

Dima Grigoriev, Nicolai Vorobjov

Research output: Contribution to journalArticlepeer-review

2 Citations (SciVal)
86 Downloads (Pure)

Abstract

We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a tropical linear variety in terms of a duality between the tropical orthogonalization A and the double tropical orthogonalization A ⊥ ⊥ of a subset A of the vector space (R∪ { ∞}) n. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

Original languageEnglish
Pages (from-to)157-174
Number of pages18
JournalApplicable Algebra in Engineering Communication and Computing
Volume32
Issue number2
Early online date29 Nov 2019
DOIs
Publication statusPublished - 31 Mar 2021

Funding

We thank M. Joswig, N. Kalinin, H. Markwig, and T. Theobald for useful discussions, and anonymous referees for constructive remarks and suggestions. Part of this research was carried out during our joint visit in September 2017 to the Hausdorff Research Institute for Mathematics at Bonn University, under the program Applied and Computational Algebraic Topology, to which we are very grateful. D. Grigoriev was partly supported by the RSF Grant 16-11-10075. Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. We thank M. Joswig, N. Kalinin, H. Markwig, and T. Theobald for useful discussions, and anonymous referees for constructive remarks and suggestions. Part of this research was carried out during our joint visit in September 2017 to the Hausdorff Research Institute for Mathematics at Bonn University, under the program Applied and Computational Algebraic Topology, to which we are very grateful. D. Grigoriev was partly supported by the RSF Grant 16-11-10075.

Keywords

  • Tropical algebra
  • Computer algebra
  • Complexity

Fingerprint

Dive into the research topics of 'Complexity of deciding whether a tropical linear prevariety is a tropical variety.'. Together they form a unique fingerprint.

Cite this