NP-Hardness of Some Linear Control Design Problems

We show that some basic linear control design problems are NP-hard, implying that, unless P=NP, they cannot be solved by polynomial time algorithms. The problems that we consider include simultaneous stabilization by output feedback, stabilization by state or output feedback in the presence of bounds on the elements of the gain matrix, and decentralized control. These results are obtained by first showing that checking the existence of a stable matrix in an interval family of matrices is NP-hard.