Computational complexity of real structured singular value in l/sub p/ setting
Soura Dasgupta, Minyue Fu · IEEE Transactions on Automatic Control · 2000
This paper studies a generalized real structured singular value (/spl mu/) problem where uncertain parameters are bounded by an l/sub p/ norm. Two results are presented. The first one shows that this generalized /spl mu/ problem is NP-hard for any given rational number p/spl isin/[1, /spl infin/]. The NP-hardness holds as long as le, the size of the largest repeated block, exceeds one. This result generalizes the known NP-hardness result for the conventional /spl mu/ problem (with p=/spl infin/). The second result, which strengthens the first one, considers the approximability problem of the generalized /spl mu/. We show that the problem of obtaining an estimate for the generalized /spl mu/ with some guaranteed bounds on the relative error remains to be NP-hard, regardless how large this bound is.