THE REAL STRUCTURED SINGULAR-VALUE IS HARDLY APPROXIMABLE

This paper investigates the problem of approximating the real structur ed 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 muc h more negative than the known NP-hard result for the problem of check ing if mu < 1. One implication of our result is that mu is hardly appr oximable in the following sense: there does not exist an algorithm, po lynomial in the size n of the mu problem, which can produce an upper b ound <(mu)over bar> for mu with the guarantee that mu less than or equ al to <(mu)over bar> less than or equal to K(n)mu for any K(n) > 0 (ev en exponential functions of n), unless NP = P. A similar statement hol ds for the lower bound of mu. Our result strengthens a recent result b y Toker, which demonstrates that obtaining a sublinear approximation f or mu is NP-hard.