IEEE Transactions on Automatic Control, Vol.45, No.9, 1762-1765, 2000
Approximating the spectral radius of sets of matrices in the max-algebra is NP-Hard
The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken From a finite set. The logarithm of the average spectral radius is traditionally called Lyapunov exponent. When one performs these products in the max-algebra, we obtain quantities that measure the performance of Discrete Event Systems. We show that approximating the lower and average max-algebraic spectral radii is NP-hard.