Static output-feedback stabilization is NP-hard

Abstract

We prove that unrestricted static output-feedback stabilization is NP-hard, already in the single-input multiple-output case. More precisely, we give a polynomial-time many-one reduction from the NP-complete Betweenness problem. Given an instance with n elements and m betweenness constraints, the reduction constructs integer matrices A∈ℤ^{D× D}, B∈ℤ^D×1, and C∈ℤ^{n× D} such that the instance is satisfiable if and only if there exists an unrestricted real row vector K∈ℝ^{1× n} for which A+BKC is Hurwitz. The state dimension is D=6(m+n), and every matrix entry has logarithmic bit length in the input size. The reduction uses one universal cubic source polynomial whose Routh determinant enforces the sign condition encoding betweenness, while fixed anchor values provide a mechanism for excluding spurious stabilizing gains of arbitrarily large magnitude. Frequency separation then compresses the simultaneous source conditions into one common affine polynomial, which is realized directly as the characteristic polynomial of A+BKC. As a by-product, deciding whether an affinely parameterized rational polynomial family contains a Hurwitz member on a rational box is NP-hard.

Computational complexity of static output feedback stabilization
Zhaobo Liu
arXiv3 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Using delays for prescribed-time static output feedback stabilization of LTI controllable and observable systems
Kang-Kang Zhang, Emilia Fridman
arXiv28 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Output feedback stabilization of ODE-heat and heat-ODE cascades with in-domain pointwise coupling
Hugo Lhachemi
Automatica5 Sep 2026Peer-reviewedPublisher termsFull textOptimisation & controlHAL
Complexity of Output Feedback Stabilization
Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang +1
arXiv20 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Data-Driven Static Output-Feedback Control for Multi-Agent Systems
Paul Serna-Torre, Adam Sedlak, Patricia Hidalgo-Gonzalez
arXiv2 Oct 2026PreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{lofberg2026static,
  title = {{Static output-feedback stabilization is NP-hard}},
  author = {Johan Löfberg},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.16886},
  eprint = {2609.16886},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.16886},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Static output-feedback stabilization is NP-hard
AU  - Johan Löfberg
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.16886
UR  - https://arxiv.org/abs/2609.16886
AB  - We prove that unrestricted static output-feedback stabilization is NP-hard, already in the single-input multiple-output case. More precisely, we give a polynomial-time many-one reduction from the NP-complete Betweenness problem. Given an instance with n elements and m betweenness constraints, the reduction constructs integer matrices A∈ℤ^D× D, B∈ℤ^D×1, and C∈ℤ^n× D such that the instance is satisfiable if and only if there exists an unrestricted real row vector K∈ℝ^1× n for which A+BKC is Hurwitz. The state dimension is D=6(m+n), and every matrix entry has logarithmic bit length in the input size. The reduction uses one universal cubic source polynomial whose Routh determinant enforces the sign condition encoding betweenness, while fixed anchor values provide a mechanism for excluding spurious stabilizing gains of arbitrarily large magnitude. Frequency separation then compresses the simultaneous source conditions into one common affine polynomial, which is realized directly as the characteristic polynomial of A+BKC. As a by-product, deciding whether an affinely parameterized rational polynomial family contains a Hurwitz member on a rational box is NP-hard.
ER  -

Abstract

Related

Cite