Braatz, Richard D. and Young, Peter M. and Doyle, John C. and Morari, Manfred (1993) Computational Complexity of μ Calculation. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechCDSTR:1993.005
![]()
|
PDF
- Submitted Version
See Usage Policy. 354kB | |
![]() |
Postscript
- Submitted Version
See Usage Policy. 41kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechCDSTR:1993.005
Abstract
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: | Report or Paper (Technical Report) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
ORCID: |
| |||||||||
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. | |||||||||
Group: | Control and Dynamical Systems Technical Reports | |||||||||
Funders: |
| |||||||||
Subject Keywords: | NP-hard, structured singular value, computational complexity | |||||||||
Record Number: | CaltechCDSTR:1993.005 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechCDSTR:1993.005 | |||||||||
Usage Policy: | You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format. | |||||||||
ID Code: | 28063 | |||||||||
Collection: | CaltechCDSTR | |||||||||
Deposited By: | Imported from CaltechCDSTR | |||||||||
Deposited On: | 01 Sep 2006 | |||||||||
Last Modified: | 03 Oct 2019 03:28 |
Repository Staff Only: item control page