The real structured singular value is hardly approximable
- 1 January 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 42 (9) , 1286-1288
- https://doi.org/10.1109/9.623094
Abstract
This paper investigates the problem of approximating the real structured singular value (real μ). A negative result is provided which shows that the problem of checking if μ=0 is NP-hard. This result is much more negative than the known NP-hard result for the problem of checking if μ0 (even exponential functions of n), unless NP=P. A similar statement holds for the lower bound of μ. Our result strengthens a recent result by Toker, which demonstrates that obtaining a sublinear approximation for μ is NP-hardKeywords
This publication has 7 references indexed in Scilit:
- On the gap between structured singular values and their upper boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the conservatism of upper bound tests for structured singular value analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrixMathematics of Control, Signals, and Systems, 1994
- Computational complexity of μ calculationIEEE Transactions on Automatic Control, 1994
- Checking robust nonsingularity is NP-hardMathematics of Control, Signals, and Systems, 1993
- Robustness in the presence of mixed parametric uncertainty and unmodeled dynamicsIEEE Transactions on Automatic Control, 1991
- Analysis of feedback systems with structured uncertaintiesIEE Proceedings D Control Theory and Applications, 1982