×

zbMATH — the first resource for mathematics

On the frontiers of polynomial computations in tropical geometry. (English) Zbl 1121.14047
Summary: 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 \(\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.

MSC:
14P99 Real algebraic and real-analytic geometry
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
14Q15 Computational aspects of higher-dimensional varieties
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Basu, S.; Pollack, R.; Roy, M.-F., Algorithms in real algebraic geometry, (2003), Springer-Verlag Berlin
[2] Bergman, G.M., The logarithmic limit-set of an algebraic variety, Trans. amer. math. soc., 157, 459-469, (1971) · Zbl 0197.17102
[3] Bogart, T., Jensen, A., Speyer, D., Sturmfels, B., Thomas, R., Computing tropical varieties. J. Symbolic. Comput., in press (doi:10.1016/j.jsc.2006.02.004) · Zbl 1121.14051
[4] Develin, M.; Sturmfels, B., Tropical convexity, Doc. math., 9, 1-27, (2004) · Zbl 1054.52004
[5] Einsiedler, M., Kapranov, M., Lind, D., 2004. Non-archimedean amoebas and tropical varieties. math.AG/0408311 · Zbl 1115.14051
[6] Einsiedler, M.; Lind, D., ()
[7] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of \(\mathcal{N} \mathcal{P}\)-completeness, (1979), Freeman
[8] Gel’fand, I.M.; Kapranov, M.M.; Zelevinsky, A.V., Discriminants, resultants, and multidimensional determinants, (1994), Birkhäuser Boston, MA · Zbl 0827.14036
[9] Grötschel, M.; Lovász, L.; Schrijver, A., ()
[10] Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. comput., 64, 1541-1555, (1995) · Zbl 0849.65030
[11] Joswig, M., Tropical halfspaces, (), 409-431 · Zbl 1090.52500
[12] Khachiyan, L.G., Polynomial algorithms in linear programming, USSR comput. math. math. phys., 20, 53-72, (1980) · Zbl 0459.90047
[13] Lee, C.W., Regular triangulations of convex polytopes, (), 443-456 · Zbl 0746.52015
[14] Mikhalkin, G., Enumerative tropical algebraic geometry in \(\mathbb{R}^2\), J. amer. math. soc., 18, 313-377, (2005) · Zbl 1092.14068
[15] Mikhalkin, G., Amoebas of algebraic varieties and tropical geometry, (), 257-300 · Zbl 1072.14013
[16] Pachter, L., Sturmfels, B., The mathematics of phylogenomics. SIAM Rev. (in press). math.ST/0409132 · Zbl 1107.92016
[17] Papadimitriou, C.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice Hall Englewood Cliffs, NY · Zbl 0503.90060
[18] Plaisted, D.A., New \(\mathcal{N} \mathcal{P}\)-hard and \(\mathcal{N} \mathcal{P}\)-complete polynomial and integer divisibility problems, Theory comput. sci., 31, 125-138, (1984) · Zbl 0572.68027
[19] Purbhoo, K., 2004. A Nullstellensatz for amoebas (preprint). Available from http://math.berkeley.edu/ kpurbhoo/
[20] Richter-Gebert, J.; Sturmfels, B.; Theobald, T., First steps in tropical geometry, (), 289-317 · Zbl 1093.14080
[21] Rojas, J.M., Stella, C.E., 2004. First steps in algorithmic fewnomial theory. math.AG/0411107
[22] Schrijver, A., ()
[23] Speyer, D., 2004. Tropical linear spaces. math.CO/0410455
[24] Speyer, D.; Sturmfels, B., The tropical Grassmannian, Adv. geom., 4, 389-411, (2004) · Zbl 1065.14071
[25] Speyer, D., Sturmfels, B., 2004. Tropical mathematics. Notes from the Clay Mathematics Institute Senior Scholar Lecture. math.CO/040899
[26] Sturmfels, B., ()
[27] Valiant, L., The complexity of computing the permanent, Theory comput. sci., 8, 189-201, (1979) · Zbl 0415.68008
[28] Viro, O., Dequantization of real algebraic geometry on logarithmic paper, (), 135-146 · Zbl 1024.14026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.