Complexity of tropical and MIN-plus linear prevarieties

DOI10.1007/s00037-013-0077-5zbMath1326.15039arXiv1204.4578OpenAlexW2077454887MaRDI QIDQ2353186

Vladimir V. Podolskii, Dima Yu. Grigoriev

Publication date: 8 July 2015

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

complexitylinear systemsolvabilityNP-completetropical algebramin-plus algebralinear system equivalencemean pay off game

Mathematics Subject Classification ID

Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Max-plus and related algebras (15A80)

Related Items (11)

Upper bounds on Betti numbers of tropical prevarieties ⋮ Idempotent and tropical mathematics; complexity of algorithms and interval analysis ⋮ Computing zero-dimensional tropical varieties via projections ⋮ Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria ⋮ Tropical combinatorial Nullstellensatz and sparse polynomials ⋮ Complexity of solving tropical linear systems ⋮ Tropical effective primary and dual Nullstellensätze ⋮ Bounds on the number of connected components for tropical prevarieties ⋮ Approximating the volume of tropical polytopes is difficult ⋮ Complexity of deciding whether a tropical linear prevariety is a tropical variety ⋮ Complexity of tropical and MIN-plus linear prevarieties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• Complexity of solving tropical linear systems
• Complexity of tropical and MIN-plus linear prevarieties
• On the frontiers of polynomial computations in tropical geometry
• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Max-linear Systems: Theory and Algorithms
• Algorithms for Parity Games
• Scheduling with AND/OR Precedence Constraints
• Computational Complexity
• Kapranov rank vs. tropical rank
• Tropical algebraic geometry

This page was built for publication: Complexity of tropical and MIN-plus linear prevarieties