Abstract
For many engineering analysis and design problems, one can think about various different types of algorithms with quite different features. Depending on the specific application, “general”, “practical”, and even “optimal” may have different meanings. In this chapter, we will be following the standards defined in the theory of computation, (Garey, Johnson (1979) Computers and intractability, a guide to the theory of NP-completeness. W. H. Freeman, San Francisco; Papadimitriou (1995) Computational complexity. Addison-Wesley/Longman, Reading), but we also would like to present an engineering interpretation of these concepts. First of all, an algorithm is considered as “general”, if it really provides a correct answer for all cases of the problem. Although this makes perfect sense from a scientific perspective, it may be too restrictive from an engineering/economical viewpoint. For example, a technique which can be used for most cases may also be considered as “general” enough. An algorithm is considered as “practical” if its execution time is reasonable. From a scientific perspective, the worst case execution time looks more appealing, but for many engineering projects average execution time may be more meaningful. Similarly, there is no universally definition for reasonable execution time, but most scientists and engineers agree that polynomial execution time is reasonable, and anything beyond that is not. In this entry, we will look at some of the classical robust control problems, and try to present an engineering interpretation of the relevant computational complexity results.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Bibliography
Aaronson S (1995) Is P versus NP formally independent? Technical report 81, EATCS
Bellare M, Rogaway P (1995) The complexity of approximating a nonlinear program. Math Program 69: 429–441
Blondel VD, Megretski A (2004) Unsolved problems in mathematical systems and control theory. Princeton University Press, Princeton
Blondel VD, Nesterov Y (2005) Computationally efficient approximations of the joint spectral radius. SIAM J Matrix Anal 27:256–272
Blondel VD, Nesterov Y (2009) Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices. SIAM J Matrix Anal 31:865–876
Blondel VD, Tsitsiklis JN (1997) NP-hardness of some linear control design problems. SIAM J Control Optim 35:2118–2127
Blondel VD, Tsitsiklis JN (2000a) The boundedness of all products of a pair of matrices is undecidable. Syst Control Lett 41:135–140
Blondel VD, Tsitsiklis JN (2000b) A survey of computational complexity results in systems and control. Automatica 36:1249–1274
Blondel VD, Sontag ED, Vidyasagar M, Willems JC (1999) Open problems in mathematical systems and control theory. Springer, London
Blondel VD, Theys J, Vladimirov AA (2003) An elementary counterexample to the finiteness conjecture. SIAM J Matrix Anal 24:963–970
Bousch T, Mairesse J (2002) Asymptotic height optimization for topical IFS, Tetris heaps and the finiteness conjecture. J Am Math Soc 15:77–111
Braatz R, Young P, Doyle J, Morari M (1994) Computational complexity of μ calculation. IEEE Trans Autom Control 39:1000–1002
Chang CT, Blondel VD (2013) An experimental study of approximation algorithms for the joint spectral radius. Numer Algorithms 64:181–202
Chen G, Church DA, Englert BG, Henkel C, Rohwedder B, Scully MO, Zubairy MS (2006) Quantum computing devices. Chapman and Hall/CRC, Boca Raton
Cook S (1971) The complexity of theorem proving procedures. In: Proceedings of the third annual ACM symposium on theory of computing, Shaker Heights, pp 151–158
Dahleh MA, Diaz-Bobillo I (1994) Control of uncertain systems. Prentice Hall, Englewood Cliffs
Dantzig G (1963) Linear programming and extensions. Princeton University Press, Princeton
Davis M (1985) Computability and unsolvability. Dover, New York
Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. W. H. Freeman, San Francisco
Hopcroft JE, Motwani R, Ullman JD (2001) Introduction to automata theory, languages, and computation. Addison Wesley, Boston
Kaye P, Laflamme R, Mosca M (2007) An introduction to quantum computing. Oxford University Press, Oxford
Kharitonov VL (1978) Asymptotic stability of an equilibrium position of a family of systems of linear differential equations. Differ Uravn 14:2086–2088
Klee V, Minty GJ (1972) How good is the simplex algorithm? In: Inequalities III (proceedings of the third symposium on inequalities), Los Angeles. Academic, New York/London, pp 159–175
Knuth DE (1997) Art of computer programming, volume 2: seminumerical algorithms, 3rd edn. Addison-Wesley, Reading
Lagarias JC, Wang Y (1995) The finiteness conjecture for the generalized spectral radius of a set of matrices. Linear Algebra Appl 214:17–42
Lewis HR, Papadimitriou CH (1998) Elements of the theory of computation. Prentice Hall, Upper Saddle River
Matiyasevich YV (1993) Hilbert’s 10th Problem. MIT, ISBN: 9780262132954. https://mitpress.mit.edu/books/hilberts-10th-problem
Nemirovskii A (1993) Several NP-hard problems arising in robust stability analysis. Math Control Signals Syst 6:99–105
Packard A, Doyle J (1993) The complex structured singular value. Automatica 29:71–109
Papadimitriou CH (1995) Computational complexity. Addison-Wesley/Longman, Reading
Poljak S, Rohn J (1993) Checking robust nonsingularity is NP-hard. Math Control Signals Syst 6:1–9
Protasov V, Jungers RM, Blondel VD (2010) Joint spectral characteristics of matrices: a conic programming approach. SIAM J Matrix Anal Appl 31:2146– 2162
Rota GC, Strang G (1960) A note on the joint spectral radius. Proc Neth Acad 22:379–381
Schrijver A (1998) Theory of linear and integer programming. Wiley, Chichester
Sipser M (2006) Introduction to the theory of computation. Thomson Course Technology, Boston
Smale S (1983) On the average number of steps in the simplex method of linear programming. Math Program 27:241–262
Toker O, Ozbay H (1996) Complexity issues in robust stability of linear delay differential systems. Math Control Signals Syst 9:386–400
Toker O, Ozbay H (1998) On the NP-hardness of the purely complex mu computation, analysis/synthesis, and some related problems in multidimensional systems. IEEE Trans Autom Control 43:409–414
Turing AM (1936) On computable numbers, with an application to the Entscheidungsproblem. Proc Lond Math Soc 42:230–265
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this entry
Cite this entry
Toker, O. (2021). Computational Complexity in Robustness Analysis and Design. In: Baillieul, J., Samad, T. (eds) Encyclopedia of Systems and Control. Springer, Cham. https://doi.org/10.1007/978-3-030-44184-5_130
Download citation
DOI: https://doi.org/10.1007/978-3-030-44184-5_130
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-44183-8
Online ISBN: 978-3-030-44184-5
eBook Packages: Intelligent Technologies and RoboticsReference Module Computer Science and Engineering