{"id":"arxiv/2609.16886","url":"https://arxiv.org/abs/2609.16886","tags":["math.OC"],"score":0,"title":"Static output-feedback stabilization is NP-hard","domain":"math.OC","source":"arxiv","authors":["Johan Löfberg"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}