Complexity of output feedback stabilization
We show that unless \(\mathrm P=\mathrm{NP}\), there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linear controller. This settles one of the best-known open problems in control theory. The result holds in both continuous and discrete time. We also present a family of stabilizable … Read more