标题： 热带矩阵分解的复杂性 显示英文标题

标题： The complexity of tropical matrix factorization

摘要： 热带算术运算在$\mathbb{R}$上由$a\oplus b=\min\{a,b\}$和$a\otimes b=a+b$定义。 设$A$为一个热带矩阵，$k$为一个正整数，热带矩阵分解（TMF）的问题是询问是否存在满足$B\otimes C=A$的热带矩阵$B\in\mathbb{R}^{m\times k}$和$C\in\mathbb{R}^{k\times n}$。我们表明，对于每个固定的$k$，TMF 的算法不太可能以多项式时间工作，从而解决了 Barvinok 在 1993 年提出的问题。 显示英文摘要

摘要： The tropical arithmetic operations on $\mathbb{R}$ are defined by $a\oplus b=\min\{a,b\}$ and $a\otimes b=a+b$. Let $A$ be a tropical matrix and $k$ a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices $B\in\mathbb{R}^{m\times k}$ and $C\in\mathbb{R}^{k\times n}$ satisfying $B\otimes C=A$. We show that no algorithm for TMF is likely to work in polynomial time for every fixed $k$, thus resolving a problem proposed by Barvinok in 1993.