Skip to content
DraconiticResearch
Search Sources API
194,161 studies31 sourcesUpdated just now
PreprintarXiv licencearXiv

Complexity of Output Feedback Stabilization

  • Amir Ali Ahmadi
  • Abraar Chaudhry
  • Ijay Narang
  • Yukai Tang
Open at sourcePDFDOICite

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.

Related

  1. Computational complexity of static output feedback stabilization
    Zhaobo Liu
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Output feedback stabilization of ODE-heat and heat-ODE cascades with in-domain pointwise coupling
    Hugo Lhachemi
    AutomaticaPeer-reviewedPublisher termsFull textOptimisation & controlHAL
  3. Static output-feedback stabilization is NP-hard
    Johan Löfberg
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. Using delays for prescribed-time static output feedback stabilization of LTI controllable and observable systems
    Kang-Kang Zhang, Emilia Fridman
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem via Output Feedback
    Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{ahmadi2026complexity,
  title = {{Complexity of Output Feedback Stabilization}},
  author = {Amir Ali Ahmadi and Abraar Chaudhry and Ijay Narang and Yukai Tang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.20636},
  eprint = {2609.20636},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20636},
}
RIS
TY  - UNPB
TI  - Complexity of Output Feedback Stabilization
AU  - Amir Ali Ahmadi
AU  - Abraar Chaudhry
AU  - Ijay Narang
AU  - Yukai Tang
PY  - 2026
DA  - 2026/09/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.20636
UR  - https://arxiv.org/abs/2609.20636
AB  - 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.
ER  -