The real structured singular value is hardly approximable
Minyue Fu · IEEE Transactions on Automatic Control · 1997
This paper investigates the problem of approximating the real structured singular value (real /spl mu/). A negative result is provided which shows that the problem of checking if /spl mu/=0 is NP-hard. This result is much more negative than the known NP-hard result for the problem of checking if /spl mu/0 (even exponential functions of n), unless NP=P. A similar statement holds for the lower bound of /spl mu/. Our result strengthens a recent result by Toker, which demonstrates that obtaining a sublinear approximation for /spl mu/ is NP-hard.