Complexity of stability and controllability of elementary hybrid systems (Q1301420)

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.