THE COMPUTATIONAL-COMPLEXITY OF APPROXIMATING THE MINIMAL PERTURBATION SCALING TO ACHIEVE INSTABILITY IN AN INTERVAL MATRIX

An interval matrix can be represented in terms of a ''center'' matrix and a nonnegative error matrix, specifying maximum elementwise perturbations from the center matrix. A commonly proposed robust stability (regularity) characterization for an interval matrix with a stable (nonsingular) center matrix identifies the minimum scaling of this error matrix for which instability (singularity) is achieved. In this paper it is shown that approximating this minimum scaling is a MAX-SNP-hard problem. This implies that in the general case, unless the class of deterministic polynomial-time decision problems, P, equals the class of non-deterministic polynomial-time decision problems, NP, thought to be highly unlikely, this minimum scaling cannot be approximated with a ratio arbitrarily close to unity in polynomial time.