Computational complexity of μ calculation
Richard P. Braatz, Peter Michael Young, John C. Doyle, Manfred Morari · IEEE Transactions on Automatic Control · 1994
The structured singular value /spl mu/ measures the robustness of uncertain systems. Numerous researchers over the last decade have worked on developing efficient methods for computing /spl mu/. This paper considers the complexity of calculating /spl mu/ with general mixed real/complex uncertainty in the framework of combinatorial complexity theory. In particular, it is proved that the /spl mu/ recognition problem with either pure real or mixed real/complex uncertainty is NP-hard. This strongly suggests that it is futile to pursue exact methods for calculating /spl mu/ of general systems with pure real or mixed uncertainty for other than small problems.>