Complexity of stability and controllability of elementary hybrid systems (Q1301420): Difference between revisions

The authors consider simple classes of nonlinear systems and prove that basic questions of stability and controllability are either undecidable or NP-hard. In the section about autonomous systems, the authors define particular classes of systems involving a simple scalar nonlinearity and prove that algorithms for deciding asymptotic stability of systems are inherently inefficient. In the section about controlled systems, they define a particular family of nonlinear systems and analyze their controllability and reachability from a computational complexity point of view. The authors introduce, as a special case, a class of hybrid systems in which the state space is partitioned into two halfspaces with different dynamics.