Metraipolis › archive › dc_ae415f9ccbdd

Static output-feedback stabilization is NP-hard — arXiv:2609.16886

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.16886
License (as archived)
CC0-1.0
Archived
2026-10-15T20:43:31.024Z
SHA-256 of the archived text
ee580631117261e5a2921b92d90aec79294c6f6a08f9bd1ece91307da357902f
Stable URL of this page
https://metraipolis.com/documento/dc_ae415f9ccbdd

How to cite

Static output-feedback stabilization is NP-hard — arXiv:2609.16886 — arXiv (en), https://arxiv.org/abs/2609.16886 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ae415f9ccbdd (Metraipolis archive dc_ae415f9ccbdd, sha256 ee580631117261e5a2921b92d90aec79294c6f6a08f9bd1ece91307da357902f)
BibTeX
@misc{dcae415f9ccbdd,
  title = {Static output-feedback stabilization is NP-hard — arXiv:2609.16886},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.16886},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ae415f9ccbdd; sha256 ee580631117261e5a2921b92d90aec79294c6f6a08f9bd1ece91307da357902f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16886. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 only if there exists an unrestricted real row vector $K\in\mathbb{R}^{1\times 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.16886 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T19:36:35.848Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).