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

DOI10.1007/S00200-019-00407-WzbMATH Open1462.14059arXiv1803.01068OpenAlexW2990631995WikidataQ126633081 ScholiaQ126633081MaRDI QIDQ2032307FDOQ2032307

Nicolai Vorobjov, Dima Grigoriev

Publication date: 11 June 2021

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1803.01068

zbMATH Keywords

complexitytropical varietytropical linear prevariety

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Max-plus and related algebras (15A80) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Foundations of tropical geometry and relations with algebra (14T10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tropical convexity
• Tropical polyhedra are equivalent to mean payoff games
• Computing tropical varieties
• Minimal half-spaces and external representation of tropical polyhedra
• Lifting tropical intersections
• Stable intersections of tropical varieties
• An algorithm for lifting points in a tropical variety
• Complexity of solving tropical linear systems
• Tropical Linear Spaces
• Tropical bases by regular projections
• On circuit valuation of matroids
• Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
• Factorization of polynomials over a finite field and the solution of systems of algebraic equations
• Complexity of tropical and MIN-plus linear prevarieties
• Algebraic, tropical, and fuzzy geometry
• Tropical noetherity and Gröbner bases
• Upper bounds on Betti numbers of tropical prevarieties
• Orthogonal tropical linear prevarieties
• Computing tropical varieties over fields with valuation
• The degree of a tropical basis
• Polynomial Complexity Recognizing a Tropical Linear Variety
• The Cayley Trick for Tropical Hypersurfaces with a View Toward Ricardian Economics

Cited In (2)

• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• The entropy of the radical ideal of a tropical curve

This page was built for publication: Complexity of deciding whether a tropical linear prevariety is a tropical variety

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032307)