Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 16, 1993 | Submitted
Report Open

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.

Additional Information

The authors thank Professor John Tsitsiklis at MIT for his comments. [R.D.B. was] supported by the Fannie and John Hertz Foundation.

Attached Files

Submitted - CDS93-005.pdf

Submitted - cds93-005.ps.gz


Files (395.5 kB)
Name Size Download all
354.0 kB Preview Download
41.5 kB Download

Additional details

August 20, 2023
October 20, 2023