A Caltech Library Service

Computational complexity of μ calculation

Braatz, Richard P. and Young, Peter M. and Doyle, John C. and Morari, Manfred (1994) Computational complexity of μ calculation. IEEE Transactions on Automatic Control, 39 (5). pp. 1994-1996. ISSN 0018-9286.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Additional Information:© Copyright 1994 IEEE. Reprinted with permission. Manuscript received July 21, 1992; revised March 25, 1993. The work of R. D. Braatz was supported by the Fannie and John Hertz Foundation. The authors thank Prof. J. Tsitsiklis at Massachusetts Institute of Technology, Cambrdige, for his comments.
Subject Keywords:computational complexity; stability
Record Number:CaltechAUTHORS:BRAieeetac94
Persistent URL:
Alternative URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5370
Deposited By: Archive Administrator
Deposited On:15 Oct 2006
Last Modified:15 Jan 2015 20:41

Repository Staff Only: item control page