On the frontiers of polynomial computations in tropical geometry

DOI10.1016/j.jsc.2005.11.006zbMath1121.14047arXivmath/0411012OpenAlexW2074004271MaRDI QIDQ2457404

Thorsten Theobald

Publication date: 23 October 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityNP-hardpolynomial time algorithmstropical varietiestropical prevarieties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of higher-dimensional varieties (14Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Real algebraic and real-analytic geometry (14P99)

Related Items

Idempotent and tropical mathematics; complexity of algorithms and interval analysis, Computing zero-dimensional tropical varieties via projections, Tropical differential equations, An algorithm for solving an overdetermined tropical linear system using the analysis of stable solutions of subsystems, On a tropical dual Nullstellensatz, Tropical combinatorial Nullstellensatz and sparse polynomials, Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians, Complexity of solving tropical linear systems, Computing tropical varieties, Tropical effective primary and dual Nullstellensätze, Tropical Cryptography, Tropical algebraic geometry in Maple: a preprocessing algorithm for finding common factors for multivariate polynomials with approximate coefficients, How many Boolean polynomials are irreducible?, Detecting tropical defects of polynomial equations, Complexity of tropical and MIN-plus linear prevarieties

Cites Work

• The complexity of computing the permanent
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Geometric algorithms and combinatorial optimization.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Tropical convexity
• Computing tropical varieties
• The Mathematics of Phylogenomics
• Non-archimedean amoebas and tropical varieties
• Polynomial algorithms in linear programming
• Enumerative tropical algebraic geometry in ℝ²
• The tropical Grassmannian
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The Logarithmic Limit-Set of an Algebraic Variety
• Algorithms in real algebraic geometry
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item