On the frontiers of polynomial computations in tropical geometry

By Thorsten Theobald. 2004

59 citations recorded by the source corpus.

We study some basic algorithmic problems concerning the intersection of tropical hypersurfaces in general dimension: deciding whether this intersection is nonempty, whether it is a tropical variety, and whether it is connected, as well as counting the number of connected components. We characterize the borderline between tractable and hard computations by proving NP-hardness and #P-hardness results under various strong restrictions of the input data, as well as providing polynomial time algorithms for various other restrictions.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Geometry and Topology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

1. Tom Diethe
2. Jeremias Knoblauch
3. Hisham Husain

In Computational Theory and Mathematics

1. Tom Diethe
2. Jeremias Knoblauch
3. Hisham Husain

In Geometry and Topology

1. Tom Diethe
2. Jeremias Knoblauch
3. Hisham Husain

Citations in the corpus

• Optimal Continual Learning has Perfect Memory and is NP-hard (2020, methodology): “This is a simple application of the results in Theobald (2006) for the case where S is the set of tropical hypersurfaces.”