On the frontiers of polynomial computations in tropical geometry

Simple item page
dc.creatorTheobald, Thorsten
dc.date2004-10-31
dc.date2005-12-20
dc.date.accessioned2026-07-07T06:38:58Z
dc.date.available2026-07-07T06:38:58Z
dc.descriptionWe 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 $\mathcal{NP}$-hardness and #$\mathcal{P}$-hardness results under various strong restrictions of the input data, as well as providing polynomial time algorithms for various other restrictions.
dc.description17 pages, 5 figures. To appear in Journal of Symbolic Computation
dc.identifierhttps://arxiv.org/abs/math/0411012
dc.identifierhttp://arxiv.org/abs/math/0411012
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/100924
dc.subjectCombinatorics
dc.subject52B70; 68W30
dc.titleOn the frontiers of polynomial computations in tropical geometry
dc.typetext

Files

Collections

arXiv