On the NP-Hardness of Checking Matrix Polytope Stability and Continuous-Time Switching Stability

Motivated by questions in robust control and switched linear dynamical systems, we consider the problem checking whether all convex combinations of $k$ matrices in $R^{n times n}$ are stable. In particular, we are interested whether there exist algorithms which can solve this problem in time polynomial in $n$ and $k$. We show that if $k= lceil n^{d} rceil $ for any fixed real $d>0$, then the problem is NP-hard, meaning that no polynomial-time algorithm in $n$ exists provided that $P ne NP$, a widely believed conjecture in computer science. On the other hand, when $k$ is a constant independent of $n$ , then it is known that the problem may be solved in polynomial time in $n$. Using these results and the method of measurable switching rules, we prove our main statement: verifying the absolute asymptotic stability of a continuous-time switched linear system with more than $n^{d}$ matrices $A_{i} in R^{n times n}$ satisfying $0 succeq A_{i} + A_{i}^{T}$ is NP-hard.