The real structured singular value is hardly approximable

This paper investigates the problem of approximating the real structured singular value (real mu). A negative result is provided which shows that the problem of checking if mu = 0 is NP-hard. This result is much more negative than the known NP-hard result for the problem of checking if mu < 1. One implication of our result is that mu is hardly approximable in the following sense: there does not exist an algorithm, polynomial in the size n of the mu problem, which can produce an upper bound <(mu)over bar> for mu with the guarantee that mu less than or equal to <(mu)over bar> less than or equal to K(n)mu for any K(n) > 0 (even exponential functions of n), unless NP = P. A similar statement holds for the lower bound of mu. Our result strengthens a recent result by Toker, which demonstrates that obtaining a sublinear approximation for mu is NP-hard.