Computational complexity of µ calculation

The structured singular value measures the robustness of uncertain systems. Numerous researchers over the last decade have worked on developing efficient methods for computing . This paper considers the complexity of calculating with general mixed real/complex uncertainty in the framework of combinatorial complexity theory. In particular, it is proved that the 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 of general systems with pure real or mixed uncertainty for other than small problems. 1 Introduction Robust stability and performance analysis with real parametric and dynamic uncertainties can be naturally formulated as a structured singular value (or ) problem, where the block structured uncertainty description is allowed to contain both real and complex blocks. It is assumed that the reader is familar with this type of robustness analysis, as space const...