Output feedback stabilization cannot be solved quickly unless p equals np
Complexity Of Output Feedback Stabilization
Computational Complexity
Summary
Controlling systems based on their outputs so they stay stable is a key problem in engineering. The authors show that finding such a controller using a linear approach cannot be done efficiently by any algorithm, unless a major theoretical breakthrough happens. This applies to both continuous-time and discrete-time systems, meaning in many common settings. They also show there are stable systems for which no quick algorithm can even write down a stabilizing controller in the usual way. This result settles a long-standing open question in control theory.
What this means in practice
- •For control system designers: Recognize when efficient algorithms for output feedback stabilization are provably impossible, helping focus efforts on approximate or heuristic methods.
- •For embedded systems engineers: Avoid relying on polynomial-time linear output feedback solvers for stabilizing controllers in resource-limited devices.
A theory result. No direct application yet.
Authors
Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang
Abstract
We show that unless P = 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 linear dynamical systems for which no polynomial-time algorithm can write down a stabilizing controller in its standard representation.