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
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Submitted Version
See Usage Policy. 354kB | |
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_postscript.png) |
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
