Idempotent and tropical mathematics. Complexity of algorithms and interval analysis
arXiv:1209.1721
Abstract
A very brief introduction to tropical and idempotent mathematics is presented. Tropical mathematics can be treated as a result of a dequantization of the traditional mathematics as the Planck constant tends to zero taking imaginary values. In the framework of idempotent mathematics usually constructions and algorithms are more simple with respect to their traditional analogs. We especially examine algorithms of tropical/idempotent mathematics generated by a collection of basic semiring (or semifield) operations and other "good" operations. Every algorithm of this type has an interval version. The complexity of this interval version coincides with the complexity of the initial algorithm. The interval version of an algorithm of this type gives exact interval estimates for the corresponding output data. Algorithms of linear algebra over idempotent and semirings are examined. In this case, basic algorithms are polynomial as well as their interval versions. This situation is very different from the traditional linear algebra, where basic algorithms are polynomial but the corresponding interval versions are NP-hard and interval estimates are not exact.
26 pages, submitted to the journal "Computers and Mathematics with Applications". arXiv admin note: substantial text overlap with arXiv:1001.4247, arXiv:1005.1247
References in corpus (7)
- Duality and separation theorems in idempotent semimodules
- Enumerative tropical algebraic geometry in R2
- The Maslov dequantization, idempotent and tropical mathematics: A brief introduction
- Interval systems over idempotent semiring
- Idempotent and tropical mathematics and problems of mathematical physics (Volume II)
- Universal algorithms, mathematics of semirings and parallel computations
- The complexity of tropical matrix factorization