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.