The real structured singular value is hardly approximable

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