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

Dima Grigoriev, Nicolai Vorobjov

OAI: oai:purehost.bath.ac.uk:publications/1e52c672-c957-4e86-a518-914eb36871f6 • DOI: https://doi.org/10.1007/s00200-019-00407-w

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∪ { ∞}) ⁿ. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

Tropical algebra Computer Algebra complexity