Kapranov rank vs. tropical rank
Authors:
- K. KimKKK. Kim
- F. RoushFRF. Roush
Open Access
- 8 February 2006
- journal article
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 134 (9) , 2487-2494
Abstract
We show that determining Kapranov rank of tropical matrices is not only NP-hard over any infinite field, but if solving Diophantine equations over the rational numbers is undecidable, then determining Kapranov rank over the rational numbers is also undecidable. We prove that Kapranov rank of tropical matrices is not bounded in terms of tropical rank, answering a question of Develin, Santos, and Sturmfels.Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Problems equivalent to rational Diophantine solvabilityJournal of Algebra, 1989
- Some algebraic and geometric computations in PSPACE1988
- The geometry of the set of characters iduced by valuations.Journal für die reine und angewandte Mathematik (Crelles Journal), 1984
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935