Skip to content

Complexity of Output Feedback Stabilization

Authors
Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang
Year
2026
Preprint
Identifiers
arXiv 2609.20636

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.

Knowledge Base

Map Tree Search

External

Document arXiv Abstract arXiv PDF arXiv HTML Google Scholar OpenAlex

Similar Papers