Computational Complexity of µ Calculation

Braatz, Richard D. and Young, Peter M. and Doyle, John C. and Morari, Manfred (1993) Computational Complexity of µ Calculation. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechCDSTR:1993.005]

Full text available as:

	PDF - Requires Adobe Acrobat Reader or other PDF viewer.
	Postscript - Requires a viewer, such as GhostView

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.

EPrint Type:	Monograph (Technical Report)
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.
Uncontrolled Keywords:	NP-hard, structured singular value, computational complexity
Subjects:	All Records
ID Code:	88
Deposited By:	Caltech Library System
Deposited On:	01 September 2006
Unique Identifier:	CaltechCDSTR:1993.005
Official Persistent URL:	http://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.

Archive Staff Only: edit this record