Computational complexity of static output feedback stabilization

We study the computational complexity of static output feedback (SOF) stabilization for continuous-time linear systems. For rational plant data, we prove that this problem is complete for the existential theory of the reals: it is equivalent, under polynomial-time transformations, to deciding whether a system of polynomial equations and inequalities with integer coefficients has a real solution. This result holds even for controllable and observable integer plants with two inputs. We characterize the effective gain dimension as the minimum number of linear combinations of gain entries that determine the characteristic polynomial for every gain. When this dimension is fixed, both feasibility testing and the construction of a rational stabilizing gain, whenever one exists, can be performed in polynomial time. SOF stabilization also remains strongly NP-hard for a family of minimal single-input integer plants. Every feasible plant in this family admits a stabilizing gain with entries in $\{-1,1\}$. For these gains, stability is preserved under simultaneous perturbations of all entries, provided that each perturbation has magnitude at most a uniform positive constant independent of the plant dimensions.