How hard is it to control switched systems?
Magnus Egerstedt, Vincent D. Blondel · 2002
We show that the problem of deciding if there exists a control that drives a switched control system between two given states is undecidable. We furthermore investigate what happens if we search for a control that achieves this in a given number of steps, or with a given number of switches. These problems are shown to be respectively NP-complete and NP-hard. The results follow as a consequence of recent complexity results on matrix mortality.