热带与最小加线性前变的计算复杂性与平均支付博弈的关联

热带和最小加线性前变的复杂性探讨了一种特殊的数学结构——热带半环，它结合了最小值（min-plus）和加法运算，常见于集合Z（包括负无穷大）或Z<${∞}$。热带代数的核心概念是研究向量x如何满足多项式的条件，如g1(x) < g2(x)，即找到最小值至少达到两次的gi(x)。在这个背景下，解决方程组gk(x) = h1(x) .. h_l(x)，其中g1(x)形式的方程组的解在min-plus代数中是一个关键问题。 本文主要关注热带线性系统，即矩阵A在热带半环上的线性约束，表现为一组不等式或方程。系统（1）中的每个元素aij+xj被定义为两者之间的最小值，而解的定义则涉及到寻找满足所有行的特定x值。特别地，该文探讨了热带线性系统可解性问题和判定两个系统等价问题的计算复杂性。这两个问题在多项式时间内可以等价于平均支付博弈的分析，表明它们属于NP问题范畴。 作者还揭示了热带线性代数与平均支付游戏之间的紧密联系，显示了在理论和实践中的重要应用价值。然而，值得注意的是，计算热带线性系统和最小加线性系统的解空间的维数已经被证明是NP-完全问题，这意味着这些任务在计算上具有较高的难度。 此外，研究结果被进一步推广到更广泛的数学领域，如Q和Q<${∞}$的情况。论文通过引入新的运算规则，如热带加法和热带乘法，展示了这些概念的通用性和广泛适用性。 总结来说，这篇论文深入研究了热带和最小加线性前变的理论基础，以及它们在实际问题中的计算复杂性和应用，强调了这一领域的理论挑战与实际问题之间的联系。这对于理解和优化热带代数算法、设计高效解决策略以及探索更深层次的数学理论具有重要意义。