Complexity of Tropical and Min-plus Linear Prevarieties
Complexity of Tropical and Min-plus Linear Prevarieties
复制标题
热带和最小加线性预品种的复杂性
DOI：
--
复制
发表时间：
2012
影响因子：
1.4
通讯作者：
V. Podolskii
中科院分区：
文献类型：
--
作者：
D. Grigoriev;V. Podolskii
热带（或min-plus）半环是一个集$${\mathbb{Z}}$$ Z（或$${\mathbb{Z \cup \{\infty\}}}$$ Z∪{∞}），具有两个运算：$${\oplus}$$⊕（通常是最小值）和$${\odot}$$⊙（通常是加法）。在热带代数中，向量x是多项式$${g_1(x) \oplus g_2(x) \oplus \cdots \oplus g_k(x)}$$ g1(x)⊕g2(x)⊕⋯⊕gk(x)的解，其中gi(x)s是热带单项式，如果mini（gi(x)）的最小值至少达到两次。在min-plus代数中，研究了$${g_1(x)\oplus \cdots \oplus g_k(x) = h_1(x)\oplus \cdots \oplus h_l(x)}$$ g1(x)⊕⋯⊕gk(x)=h1(x)⊕⋯⊕hl(x)形式方程组的解。本文研究了热带线性系统的计算问题。我们证明了可解性问题（在$${\mathbb{Z}}$$ Z和$${\mathbb{Z} \cup \{\infty\}}$$ Z∪{∞}上）和确定两个线性系统的等价性问题（在$${\mathbb{Z}}$$ Z和$${\mathbb{Z} \cup \{\infty\}}$$ Z∪{∞}上）在多项式时间约简下等价于平均收益博弈，也等价于min-plus代数中的类似问题。特别地，所有这些问题都属于$${\mathsf{NP}\cap \mathsf{coNP}}$$ NP∩coNP。因此，我们提供了热带线性代数与平均收益博弈和最小加线性代数的计算方面的紧密联系。另一方面，我们证明了热带线性系统和最小+线性系统解空间的维数计算是$${\mathsf{NP}}$$ NP完全的。
A tropical (or min-plus) semiring is a set $${\mathbb{Z}}$$Z (or $${\mathbb{Z \cup \{\infty\}}}$$Z∪{∞}) endowed with two operations: $${\oplus}$$⊕ , which is just usual minimum, and $${\odot}$$⊙ , which is usual addition. In tropical algebra, a vector x is a solution to a polynomial $${g_1(x) \oplus g_2(x) \oplus \cdots \oplus g_k(x)}$$g1(x)⊕g2(x)⊕⋯⊕gk(x) , where the gi(x)s are tropical monomials, if the minimum in mini(gi(x)) is attained at least twice. In min-plus algebra solutions of systems of equations of the form $${g_1(x)\oplus \cdots \oplus g_k(x) = h_1(x)\oplus \cdots \oplus h_l(x)}$$g1(x)⊕⋯⊕gk(x)=h1(x)⊕⋯⊕hl(x) are studied.In this paper, we consider computational problems related to tropical linear system. We show that the solvability problem (both over $${\mathbb{Z}}$$Z and $${\mathbb{Z} \cup \{\infty\}}$$Z∪{∞}) and the problem of deciding the equivalence of two linear systems (both over $${\mathbb{Z}}$$Z and $${\mathbb{Z} \cup \{\infty\}}$$Z∪{∞}) are equivalent under polynomial-time reductions to mean payoff games and are also equivalent to analogous problems in min-plus algebra. In particular, all these problems belong to $${\mathsf{NP}\cap \mathsf{coNP}}$$NP∩coNP . Thus, we provide a tight connection of computational aspects of tropical linear algebra with mean payoff games and min-plus linear algebra. On the other hand, we show that computing the dimension of the solution space of a tropical linear system and of a min-plus linear system is $${\mathsf{NP}}$$NP -complete.