The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix (Q1894653)

A typical approach to characterizing robust stability (regularity) of an interval matrix with a stable (nonsingular) center matrix is to compute the minimum scaling of the nonnegative error matrix (specifying maximum elementwise perturbations from the center matrix) for which instability (singularity) is achieved. Here, it is shown that approximating this minimum scaling is a MAX-SNP-hard problem. This implies that in general, unless the class of deterministic polynomial-time decision problems equals the class of nondeterministic polynomial-time decision problems (not likely), this minimum scaling cannot be approximated with a ratio arbitrarily close to unity in polynomial time. As an intermediate step in deriving this result, a class of interval matrix families is exhibited for which regularity and robust stability are equivalent. This is a generalization of an earlier result [\textit{A. Nemirovskij}, Math. Control Signals Syst. 6, 99-105 (1993; Zbl 0792.93100)], and may be of independent interest in the study of robust stability problems for interval matrices.