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

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^{\perp }$ and the double tropical orthogonalization $A^{\perp \perp }$ of a subset $A$ of the vector space $(\mathbb{R}\cup \{\infty \}{)}^n$. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

15 pages