论文标题
给定双线性系统的增长率是否为1是不可决定的
It is undecidable whether the growth rate of a given bilinear system is 1
论文作者
论文摘要
我们表明，如果$（b，v）$的增长率为$ 1 $，则没有任何算法决定任何双线性系统$（b，v）$。这回答了一个BUI的问题，该问题表明，如果系数为正，则可以计算增长率（即，有一种算法输出了$（B，V）$的数字序列。我们的证明是基于减少一组矩阵的关节光谱半径的计算，以计算双线性系统的生长速率。我们还使用还原来推断没有算法近似于具有相对精确度的双线性系统的增长率$ \ varepsilon $在系统的大小和$ \ varepsilon $的时间多项式上。即使所有系数都是非负合理的，我们的两个结果也会成立。
We show that there exists no algorithm that decides for any bilinear system $(B,v)$ if the growth rate of $(B,v)$ is $1$. This answers a question of Bui who showed that if the coefficients are positive the growth rate is computable (i.e., there is an algorithm that outputs the sequence of digits of the growth rate of $(B,v)$). Our proof is based on a reduction of the computation of the joint spectral radius of a set of matrices to the computation of the growth rate of a bilinear system. We also use our reduction to deduce that there exists no algorithm that approximates the growth rate of a bilinear system with relative accuracy $\varepsilon$ in time polynomial in the size of the system and of $\varepsilon$. Our two results hold even if all the coefficients are nonnegative rationals.
