{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:36:30Z","timestamp":1742942190086,"version":"3.40.3"},"publisher-location":"London","reference-count":37,"publisher":"Springer London","isbn-type":[{"type":"electronic","value":"9781447151029"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-1-4471-5102-9_130-2","type":"book-chapter","created":{"date-parts":[[2014,10,2]],"date-time":"2014-10-02T02:12:15Z","timestamp":1412215935000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity Issues in Robust Control"],"prefix":"10.1007","author":[{"given":"Onur","family":"Toker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,3,7]]},"reference":[{"key":"130-2_CR1","unstructured":"Aaronson S (1995) Is P versus NP formally independent? Technical report 81, EATCS"},{"key":"130-2_CR2","first-page":"429","volume":"69","author":"M Bellare","year":"1995","unstructured":"Bellare M, Rogaway P (1995) The complexity of approximating a nonlinear program. Math Program 69:429\u2013441","journal-title":"Math Program"},{"key":"130-2_CR3","doi-asserted-by":"crossref","DOI":"10.1515\/9781400826155","volume-title":"Unsolved problems in mathematical systems and control theory","author":"VD Blondel","year":"2004","unstructured":"Blondel VD, Megretski A (2004) Unsolved problems in mathematical systems and control theory. Princeton University Press, Princeton"},{"key":"130-2_CR4","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/040607009","volume":"27","author":"VD Blondel","year":"2005","unstructured":"Blondel VD, Nesterov Y (2005) Computationally efficient approximations of the joint spectral radius. SIAM J Matrix Anal 27:256\u2013272","journal-title":"SIAM J Matrix Anal"},{"key":"130-2_CR5","doi-asserted-by":"publisher","first-page":"2118","DOI":"10.1137\/S0363012994272630","volume":"35","author":"VD Blondel","year":"1997","unstructured":"Blondel VD, Tsitsiklis JN (1997) NP-hardness of some linear control design problems. SIAM J Control Optim 35:2118\u20132127","journal-title":"SIAM J Control Optim"},{"key":"130-2_CR6","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0167-6911(00)00049-9","volume":"41","author":"VD Blondel","year":"2000","unstructured":"Blondel VD, Tsitsiklis JN (2000a) The boundedness of all products of a pair of matrices is undecidable. Syst Control Lett 41:135\u2013140","journal-title":"Syst Control Lett"},{"key":"130-2_CR7","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1016\/S0005-1098(00)00050-9","volume":"36","author":"VD Blondel","year":"2000","unstructured":"Blondel VD, Tsitsiklis JN (2000b) A survey of computational complexity results in systems and control. Automatica 36:1249\u20131274","journal-title":"Automatica"},{"key":"130-2_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0807-8","volume-title":"Open problems in mathematical systems and control theory","author":"VD Blondel","year":"1999","unstructured":"Blondel VD, Sontag ED, Vidyasagar M, Willems JC (1999) Open problems in mathematical systems and control theory. Springer, London"},{"key":"130-2_CR9","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1006\/jcss.2000.1737","volume":"62","author":"VD Blondel","year":"2001","unstructured":"Blondel VD, Bournez O, Koiran P, Tsitsiklis JN (2001) The stability of saturated linear dynamical systems is undecidable. J Comput Syst Sci 62:442\u2013462","journal-title":"J Comput Syst Sci"},{"key":"130-2_CR10","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/S0895479801397846","volume":"24","author":"VD Blondel","year":"2003","unstructured":"Blondel VD, Theys J, Vladimirov AA (2003) An elementary counterexample to the finiteness conjecture. SIAM J Matrix Anal 24:963\u2013970","journal-title":"SIAM J Matrix Anal"},{"key":"130-2_CR11","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1090\/S0894-0347-01-00378-2","volume":"15","author":"T Bousch","year":"2002","unstructured":"Bousch T, Mairesse J (2002) Asymptotic height optimization for topical IFS, Tetris heaps and the finiteness conjecture. J Am Math Soc 15:77\u2013111","journal-title":"J Am Math Soc"},{"key":"130-2_CR12","doi-asserted-by":"publisher","first-page":"1000","DOI":"10.1109\/9.284879","volume":"39","author":"R Braatz","year":"1994","unstructured":"Braatz R, Young P, Doyle J, Morari M (1994) Computational complexity of \u03bc calculation. IEEE Trans Autom Control 39:1000\u20131002","journal-title":"IEEE Trans Autom Control"},{"key":"130-2_CR13","doi-asserted-by":"crossref","DOI":"10.1201\/9781420011777","volume-title":"Quantum computing devices","author":"G Chen","year":"2006","unstructured":"Chen G, Church DA, Englert BG, Henkel C, Rohwedder B, Scully MO, Zubairy MS (2006) Quantum computing devices. Chapman and Hall\/CRC, Boca Raton"},{"key":"130-2_CR14","first-page":"151","volume-title":"The complexity of theorem proving procedures","author":"S Cook","year":"1971","unstructured":"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\u2013158"},{"key":"130-2_CR15","volume-title":"Control of uncertain systems","author":"MA Dahleh","year":"1994","unstructured":"Dahleh MA, Diaz-Bobillo I (1994) Control of uncertain systems. Prentice Hall, Englewood Cliffs"},{"key":"130-2_CR16","volume-title":"Linear programming and extensions","author":"G Dantzig","year":"1963","unstructured":"Dantzig G (1963) Linear programming and extensions. Princeton University Press, Princeton"},{"key":"130-2_CR17","unstructured":"Davis M (1985) Computability and unsolvability. Dover"},{"key":"130-2_CR18","volume-title":"Computers and intractability, a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. W. H. Freeman, San Francisco"},{"key":"130-2_CR19","volume-title":"Introduction to automata theory, languages, and computation","author":"JE Hopcroft","year":"2001","unstructured":"Hopcroft JE, Motwani R, Ullman JD (2001) Introduction to automata theory, languages, and computation. Addison Wesley, Boston"},{"key":"130-2_CR20","volume-title":"An introduction to quantum computing","author":"P Kaye","year":"2007","unstructured":"Kaye P, Laflamme R, Mosca M (2007) An introduction to quantum computing. Oxford University Press, Oxford"},{"key":"130-2_CR21","first-page":"2086","volume":"14","author":"VL Kharitonov","year":"1978","unstructured":"Kharitonov VL (1978) Asymptotic stability of an equilibrium position of a family of systems of linear differential equations. Differentsial\u2019nye Uravneniya 14:2086\u20132088","journal-title":"Differentsial\u2019nye Uravneniya"},{"key":"130-2_CR22","first-page":"159","volume-title":"How good is the simplex algorithm? In: Inequalities III (proceedings of the third symposium on inequalities)","author":"V Klee","year":"1972","unstructured":"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\u2013175"},{"key":"130-2_CR23","volume-title":"Art of computer programming, volume 2: seminumerical algorithms","author":"DE Knuth","year":"1997","unstructured":"Knuth DE (1997) Art of computer programming, volume 2: seminumerical algorithms, 3rd edn. Addison-Wesley, Reading","edition":"3"},{"key":"130-2_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0024-3795(93)00052-2","volume":"214","author":"JC Lagarias","year":"1995","unstructured":"Lagarias JC, Wang Y (1995) The finiteness conjecture for the generalized spectral radius of a set of matrices. Linear Algebra Appl 214:17\u201342","journal-title":"Linear Algebra Appl"},{"key":"130-2_CR25","volume-title":"Elements of the theory of computation","author":"HR Lewis","year":"1998","unstructured":"Lewis HR, Papadimitriou CH (1998) Elements of the theory of computation. Prentice Hall, Upper Saddle River"},{"key":"130-2_CR26","unstructured":"Matiyasevich YV (1993) Quantum computing devices. MIT"},{"key":"130-2_CR27","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01211741","volume":"6","author":"A Nemirovskii","year":"1993","unstructured":"Nemirovskii A (1993) Several NP-hard problems arising in robust stability analysis. Math Control Signals Syst 6:99\u2013105","journal-title":"Math Control Signals Syst"},{"key":"130-2_CR28","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0005-1098(93)90175-S","volume":"29","author":"A Packard","year":"1993","unstructured":"Packard A, Doyle J (1993) The complex structured singular value. Automatica 29:71\u2013109","journal-title":"Automatica"},{"key":"130-2_CR29","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1995","unstructured":"Papadimitriou CH (1995) Computational complexity. Addison-Wesley\/Longman, Reading"},{"key":"130-2_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01213466","volume":"6","author":"S Poljak","year":"1993","unstructured":"Poljak S, Rohn J (1993) Checking robust nonsingularity is NP-hard. Math Control Signals Syst 6:1\u20139","journal-title":"Math Control Signals Syst"},{"key":"130-2_CR31","first-page":"379","volume":"22","author":"GC Rota","year":"1960","unstructured":"Rota GC, Strang G (1960) A note on the joint spectral radius. Proc Neth Acad 22:379\u2013381","journal-title":"Proc Neth Acad"},{"key":"130-2_CR32","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver A (1998) Theory of linear and integer programming. Wiley, Chichester"},{"key":"130-2_CR33","volume-title":"Introduction to the theory of computation","author":"M Sipser","year":"2006","unstructured":"Sipser M (2006) Introduction to the theory of computation. Thomson Course Technology, Boston"},{"key":"130-2_CR34","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02591902","volume":"27","author":"S Smale","year":"1983","unstructured":"Smale S (1983) On the average number of steps in the simplex method of linear programming. Math Program 27:241\u2013262","journal-title":"Math Program"},{"key":"130-2_CR35","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/BF01211858","volume":"9","author":"O Toker","year":"1996","unstructured":"Toker O, Ozbay H (1996) Complexity issues in robust stability of linear delay differential systems. Math Control Signals Syst 9:386\u2013400","journal-title":"Math Control Signals Syst"},{"key":"130-2_CR36","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1109\/9.661609","volume":"43","author":"O Toker","year":"1998","unstructured":"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\u2013414","journal-title":"IEEE Trans Autom Control"},{"key":"130-2_CR37","first-page":"230","volume":"42","author":"AM Turing","year":"1936","unstructured":"Turing AM (1936) On computable numbers, with an application to the Entscheidungsproblem. Proc Lond Math Soc 42:230\u2013265","journal-title":"Proc Lond Math Soc"}],"container-title":["Encyclopedia of Systems and Control"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4471-5102-9_130-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,9]],"date-time":"2023-02-09T22:45:57Z","timestamp":1675982757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-1-4471-5102-9_130-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9781447151029"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-1-4471-5102-9_130-2","relation":{},"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 March 2014, 16:22:18","order":1,"name":"received","label":"Received","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"3 March 2014, 16:22:18","order":2,"name":"accepted","label":"Accepted","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"7 March 2014","order":3,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}