{"id":"arxiv/2609.20636","url":"https://arxiv.org/abs/2609.20636","tags":["math.OC","cs.CC","eess.SY"],"score":0,"title":"Complexity of Output Feedback Stabilization","domain":"math.OC","source":"arxiv","authors":["Amir Ali Ahmadi","Abraar Chaudhry","Ijay Narang","Yukai Tang"],"reviews":0,"subject":"math.OC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}