NP-hardness of unrestricted static output-feedback stabilization
An instance consists of positive integers $n, m, p$ and rational matrices $A \in \mathbb{Q}^{n \times n}$, $B \in \mathbb{Q}^{n \times m}$ and $C \in \mathbb{Q}^{p \times n}$, encoded in binary. It is a yes-instance when some real matrix $K \in \mathbb{R}^{m \times p}$, with no constraints on its entries, satisfies $$\operatorname{Re} \lambda < 0 \qquad \text{for every eigenvalue } \lambda \text{ of } A + BKC,$$ that is, when the system $\dot x = Ax + Bu$, $y = Cx$ can be stabilized by static output feedback $u = Ky$. For state feedback ($C = I$) such a $K$ exists exactly when the pair $(A, B)$ is stabilizable. Blondel and Tsitsiklis proved the problem NP-hard when the entries of $K$ are confined to prescribed intervals, even for state feedback; they could not establish its complexity without such constraints, and conjectured that it is NP-hard as well.
Problem. Is this decision problem NP-hard under polynomial-time many-one reductions, in the binary encoding of the rational input?
Source: Blondel and Tsitsiklis (1997), §1, who conjecture that stabilization by static output feedback is NP-hard without constraints on the gain; posed as Open Problem 1 in Blondel and Tsitsiklis (1999); stated by OpenProblemsInNLA as a decision problem on rational input in binary, under polynomial-time many-one reductions.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- NA
- Keywords
- Hurwitz matrices, NP-hardness, OpenProblemsInNLA, static output feedback
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@incollection{blondel1999,
author = {Blondel, Vincent D. and Tsitsiklis, John N.},
title = {Three problems on the decidability and complexity of stability},
booktitle = {Open Problems in Mathematical Systems and Control Theory},
editor = {Blondel, Vincent and Sontag, Eduardo D. and Vidyasagar, Mathukumalli and Willems, Jan C.},
series = {Communications and Control Engineering},
publisher = {Springer},
address = {London},
year = {1999},
pages = {45--51},
doi = {10.1007/978-1-4471-0807-8_11},
}
@article{blondel1997,
author = {Blondel, Vincent and Tsitsiklis, John N.},
title = {{NP}-Hardness of Some Linear Control Design Problems},
journal = {SIAM J. Control Optim.},
volume = {35},
number = {6},
year = {1997},
pages = {2118--2127},
doi = {10.1137/S0363012994272630},
}
@misc{openproblemsinnla-mf08,
author = {Townsend, Alex},
title = {{MF-08}: NP-hardness of unrestricted static output-feedback stabilization},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/matrix-functions-and-stability/MF-08/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
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 …
In this paper we give a polynomial-time reduction from the Subset Sum Problem to unconstrained static output feedback stabilization, establishing its NP-hardness. The construction uses two scalar building blocks to impose approximate discrete choices and a weighted-sum constraint. Once the problem is encoded, we relate the stability of the $N+1$ decoupled loops encoding the problem to that of a coupled …
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 …
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\in\mathbb Z^{D\times D}$, $B\in\mathbb Z^{D\times1}$, and $C\in\mathbb Z^{n\times D}$ such that the instance is satisfiable if and …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00232, "NP-hardness of unrestricted static output-feedback stabilization", clopen.solutions.