{"ID":23507379,"CreatedAt":"2026-09-18T02:21:44.056544415Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20636","arxiv_id":"2609.20636","title":"Complexity Of Output Feedback Stabilization","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2609.20636","url_pdf":"https://arxiv.org/pdf/2609.20636v1","authors":"[\"Amir Ali Ahmadi\",\"Abraar Chaudhry\",\"Ijay Narang\",\"Yukai Tang\"]","published":"2026-09-17T16:21:49Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.CC\",\"eess.SY\"]","methods":"[]","has_code":false}