Computing the cube of an interval matrix is NP-Hard
Olga M. Kosheleva, Владик Крейнович, Günter Mayer, Hung T. Nguyen · 2005
In many practical applications, we are interested in computing the product of given matrices and/or a power of a given matrix. In some cases, the initial matrices are only known with interval uncertainty. It turns out that under this uncertainty, there is a principal difference between the product of two matrices and the product of three (or more) matrices:• on the one hand, it is more or less known that the problems of computing the exact range for the product of two matrices - and for the square of a matrix - are computationally feasible;• on the other hand, we prove that the problems of computing the exact ranges for the product of three matrices - and for the third power of a matrix - are NP-hard.