NP-HARDNESS OF SOME LINEAR-CONTROL DESIGN-PROBLEMS

We show that some basic linear control design problems are NP-hard, im plying that, unless P=NP, they cannot be solved by polynomial time alg orithms. The problems that we consider include simultaneous stabilizat ion by output feedback, stabilization by state or output feedback in t he presence of bounds on the elements of the gain matrix, and decentra lized control. These results are obtained by first showing that checki ng the existence of a stable matrix in an interval family of matrices is NP-hard.