From linear to nonlinear: some complexity comparisons

From linear to nonlinear: some complexity comparisons. Sontag, E. In Proc. IEEE Conf. Decision and Control, New Orleans, Dec. 1995, IEEE Publications, 1995, pages 2916–2920, 1995.
abstract bibtex

This paper deals with the computational complexity, and in some cases undecidability, of several problems in nonlinear control. The objective is to compare the theoretical difficulty of solving such problems to the corresponding problems for linear systems. In particular, the problem of null-controllability for systems with saturations (of a "neural network" type) is mentioned, as well as problems regarding piecewise linear (hybrid) systems. A comparison of accessibility, which can be checked fairly simply by Lie-algebraic methods, and controllability, which is at least NP-hard for bilinear systems, is carried out. Finally, some remarks are given on analog computation in this context.

@INPROCEEDINGS{95cdc-complexity,
   AUTHOR       = {E.D. Sontag},
   BOOKTITLE    = {Proc. IEEE Conf. Decision and Control, New Orleans, Dec. 1995, IEEE Publications, 1995},
   TITLE        = {From linear to nonlinear: some complexity comparisons},
   YEAR         = {1995},
   OPTADDRESS   = {},
   OPTCROSSREF  = {},
   OPTEDITOR    = {},
   OPTMONTH     = {},
   OPTNOTE      = {},
   OPTNUMBER    = {},
   OPTORGANIZATION = {},
   PAGES        = {2916--2920},
   OPTPUBLISHER = {},
   OPTSERIES    = {},
   OPTVOLUME    = {},
   KEYWORDS     = {theory of computing and complexity, 
      computational complexity, controllability, observability},
   PDF          = {../../FTPDIR/95cdc-complexity.pdf},
   ABSTRACT     = { This paper deals with the computational complexity, and 
      in some cases undecidability, of several problems in nonlinear 
      control. The objective is to compare the theoretical difficulty of 
      solving such problems to the corresponding problems for linear 
      systems. In particular, the problem of null-controllability for 
      systems with saturations (of a "neural network" type) is mentioned, 
      as well as problems regarding piecewise linear (hybrid) systems. A 
      comparison of accessibility, which can be checked fairly simply by 
      Lie-algebraic methods, and controllability, which is at least NP-hard 
      for bilinear systems, is carried out. Finally, some remarks are given 
      on analog computation in this context. }
}

Downloads: 0

{"_id":"MzhmRYq5sbeWshnvN","bibbaseid":"sontag-fromlineartononlinearsomecomplexitycomparisons-1995","downloads":0,"creationDate":"2018-10-18T05:07:06.485Z","title":"From linear to nonlinear: some complexity comparisons","author_short":["Sontag, E."],"year":1995,"bibtype":"inproceedings","biburl":"http://www.sontaglab.org/PUBDIR/Biblio/complete-bibliography.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["E.D."],"propositions":[],"lastnames":["Sontag"],"suffixes":[]}],"booktitle":"Proc. IEEE Conf. Decision and Control, New Orleans, Dec. 1995, IEEE Publications, 1995","title":"From linear to nonlinear: some complexity comparisons","year":"1995","optaddress":"","optcrossref":"","opteditor":"","optmonth":"","optnote":"","optnumber":"","optorganization":"","pages":"2916–2920","optpublisher":"","optseries":"","optvolume":"","keywords":"theory of computing and complexity, computational complexity, controllability, observability","pdf":"../../FTPDIR/95cdc-complexity.pdf","abstract":"This paper deals with the computational complexity, and in some cases undecidability, of several problems in nonlinear control. The objective is to compare the theoretical difficulty of solving such problems to the corresponding problems for linear systems. In particular, the problem of null-controllability for systems with saturations (of a \"neural network\" type) is mentioned, as well as problems regarding piecewise linear (hybrid) systems. A comparison of accessibility, which can be checked fairly simply by Lie-algebraic methods, and controllability, which is at least NP-hard for bilinear systems, is carried out. Finally, some remarks are given on analog computation in this context. ","bibtex":"@INPROCEEDINGS{95cdc-complexity,\n AUTHOR = {E.D. Sontag},\n BOOKTITLE = {Proc. IEEE Conf. Decision and Control, New Orleans, Dec. 1995, IEEE Publications, 1995},\n TITLE = {From linear to nonlinear: some complexity comparisons},\n YEAR = {1995},\n OPTADDRESS = {},\n OPTCROSSREF = {},\n OPTEDITOR = {},\n OPTMONTH = {},\n OPTNOTE = {},\n OPTNUMBER = {},\n OPTORGANIZATION = {},\n PAGES = {2916--2920},\n OPTPUBLISHER = {},\n OPTSERIES = {},\n OPTVOLUME = {},\n KEYWORDS = {theory of computing and complexity, \n computational complexity, controllability, observability},\n PDF = {../../FTPDIR/95cdc-complexity.pdf},\n ABSTRACT = { This paper deals with the computational complexity, and \n in some cases undecidability, of several problems in nonlinear \n control. The objective is to compare the theoretical difficulty of \n solving such problems to the corresponding problems for linear \n systems. In particular, the problem of null-controllability for \n systems with saturations (of a \"neural network\" type) is mentioned, \n as well as problems regarding piecewise linear (hybrid) systems. A \n comparison of accessibility, which can be checked fairly simply by \n Lie-algebraic methods, and controllability, which is at least NP-hard \n for bilinear systems, is carried out. Finally, some remarks are given \n on analog computation in this context. }\n}\n\n","author_short":["Sontag, E."],"key":"95cdc-complexity","id":"95cdc-complexity","bibbaseid":"sontag-fromlineartononlinearsomecomplexitycomparisons-1995","role":"author","urls":{},"keyword":["theory of computing and complexity","computational complexity","controllability","observability"],"downloads":0,"html":""},"search_terms":["linear","nonlinear","complexity","comparisons","sontag"],"keywords":["theory of computing and complexity","computational complexity","controllability","observability"],"authorIDs":[],"dataSources":["DKqZbTmd7peqE4THw"]}