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

Dima Grigoriev, Nicolai Vorobjov

Research output: Contribution to journalArticle

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)1-18
Number of pages18
JournalApplicable Algebra in Engineering Communication and Computing
Early online date29 Nov 2019
DOIs
Publication statusE-pub ahead of print - 29 Nov 2019

Keywords

  • Tropical algebra
  • Computer algebra
  • Complexity

Profiles

Cite this