Complexity of Output Feedback Stabilization

Abraar Chaudhry; Amir Ali Ahmadi; Ijay Narang; Yukai Tang

REVIEW

Complexity of Output Feedback Stabilization

Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang

Optimization and Control · Submitted 17 Sep 2026

Pith's verdict: Settles a long-standing open problem in control theory with a clean reduction; deserves serious review.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 20, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.20636 (version 2)

Pith IDD7MOT7Z4, Pith's permanent record of this paper and its review

CitationAbraar Chaudhry, Amir Ali Ahmadi, Ijay Narang, Yukai Tang. "Complexity of Output Feedback Stabilization." arXiv:2609.20636 (2026). https://pith.science/paper/D7MOT7Z4

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

This paper proves that output feedback stabilization is strongly NP-hard, resolving the problem Blondel, Gevers, and Lindquist called the most often mentioned open problem in systems and control. The reduction from 3SAT is explicit, the gluing lemma is a new technical tool, and the result holds for both continuous and discrete time. The representation obstruction (Section 4) is an independent bonus: it shows that even when stabilization is possible, writing down a stabilizing controller in standard binary requires exponential space—making the problem unlikely to be in NP. These are real contributions.

The proof is rigorous in structure and the authors have been transparent about using an AI assistant to reach the final form. I checked the main steps: the construction of the simultaneous stabilization instances in Step 1, the gluing lemma with its eigenvalue separation condition (h = 4096m), and the application of Lemma 2 to relate Hurwitzness to Lyapunov certificates. The discrete-time conversion via Cayley transform is standard but the specific parameter choice (τ = hm(m+1)) to keep denominators polynomial is a careful engineering detail. The stress-test note flagged a likely typo in the definition of λ_i in Section 3 (dividing by i-1 when i=1); this does not affect correctness and is easy to fix.

My main caution is about checking the constants in the gluing lemma: the bound 12mβ²/h assumes h ≥ 4 and the argument seems sound, but a referee should verify that the block-row-sum bound in (7) indeed holds under the conditions stated, especially when combined with the discrete-time construction where τ is O(m³). The integer size bounds in the discrete-time case rely on τ² and N⁴, which are polynomial; I did not see a hidden exponential. The claim that multi-output extensions are trivial is plausible but could use a brief justification.

That said, the central argument appears to hold up. The paper is well within the standard of a rigorous mathematical proof of NP-hardness and the representation obstruction is a standalone contribution. I would bring this to a reading group and cite it once published.

Recommendation: send to peer review. The paper deserves a careful referee who can check the matrix constructions and the bound calculations, but the result is important enough to warrant the effort.

Referee report

Major objections (3)

[Section 3, equation (18)] The definition λ_i = τ/(i-1) for i = 1,…,m is undefined for i=1. From the context (e.g., the subsequent requirement that 1+λ_i = τ/i), the intended definition appears to be λ_i = τ/i − 1. This typographical error should be corrected, as the discrete-time construction relies on these parameters.
[Lemma 2(i)] The proof states that MH+HM^T = -2(HC^T)(HC^T)^T without intermediate steps. Although the claim is plausible, the reader is left to verify a nontrivial algebraic identity. The authors should either provide a brief verification (using the relations in (3) and the definitions of M, H, C) or cite a known result. This would improve the transparency of the argument.
[Proof of Lemma 3] The bound ‖X−G_0‖ ≤ 12mβ^2/h is derived under the assumption h≥4 (so that |λ_i-λ_j|−2 ≥ h/2). This condition is satisfied in the constructions. However, the derivation uses the inequality ∥X_{ii}-G_i∥ ≤ 2∑_{j≠i} ∥X_{ij}∥, which implicitly assumes that the matrix Γ(t_i) defined in the proof has norm at most 2∥t_i∥. This step is correct but would benefit from a brief justification.

Minor objections (6)

[Header and abstract] The title in the header contains extra spaces: 'OUPUT FEEDBACK ST ABILIZA TION'. Please correct the formatting.
[Section 2, after equation (1)] The definition of J appears as 'J= (0 0; 1 0)'. For clarity, use matrix notation: J = [[0,0],[1,0]].
[Lemma 2 proof] In the derivation of MH+HM^T, the notation '−2(HC T)(HC T) T' has missing parentheses and typos. Please format properly as −2(HC^T)(HC^T)^T.
[Section 3, after equation (18)] Set τ = hm(m+1). For completeness, explicitly note that τ is an integer and that all λ_i are distinct.
[Proof of Theorem 7] The bound (20) states 0 < x_n ≤ (2/3) 2^{-2n}. The subsequent denominator bound b ≥ (3/2) 2^{2n} follows only if one assumes a ≥ 1 in a/b. This is correct because x_n > 0, but it may be helpful to state explicitly that the numerator is a positive integer.
[References] Reference [4] includes a URL; ensure it is accessible. Consider adding a note that the link was verified as of submission.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Output feedback stabilization is strongly NP-hard, resolving a three-decade open problem in control theory.

The reading

For thirty years, control theorists have asked whether there is an efficient algorithm to decide if a linear system can be stabilized using only its outputs. This paper proves that the problem is strongly NP-hard, meaning that unless P = NP, no polynomial-time (or even pseudo-polynomial-time) algorithm exists. The result holds for both continuous and discrete time. Moreover, even when a stabilizing controller exists, the paper shows that writing it down can require exponentially many bits, so no polynomial-time algorithm can output a standard representation of a stabilizing controller.

What carries the argument

The central tool is a block matrix M of the form [[0, -D - u c^T], [I, -v c^T]] whose Hurwitzness is tied to the positive definiteness of a symmetric matrix X satisfying the linear equations Xc = v and D X - X D^T = v u^T - u v^T. Lemma 2 gives this equivalence: if M is Hurwitz then X is positive semidefinite; if X is positive definite and sym(D + u c^T) is positive definite then M is Hurwitz. Lemma 3 (the gluing lemma) constructs the unique X that solves these equations and shows it is close to a block-diagonal matrix G0 when the eigenvalues λ_i are well separated, preserving the (1,1) entries that encode the 3SAT variables. Lemma 4 maps Boolean assignments to the vectors u_i, v_i and their associated G_i matrices so that satisfiability corresponds to positive semidefiniteness of all G_i.

Extended reading notes

Core claim

The paper establishes that the output feedback stabilization problem—deciding whether there exists a matrix K such that A + BKC is Hurwitz (continuous time) or Schur (discrete time)—is strongly NP-hard. The proof reduces 3SAT to the stabilization problem via a two-step construction. Step 1 encodes the Boolean formula into a simultaneous stabilization problem for multiple small systems, using affine functions of the variables that track clause satisfaction. Step 2 glues those systems into a single large system using a technical lemma (Lemma 3) that controls the interaction between blocks when the eigenvalues of the open-loop dynamics are widely spaced. A separate family of systems (Theorems 7 and 8) shows a representation obstruction: a stabilizing controller exists, but any rational controller requires a denominator with exponentially many bits, so it cannot be written down in polynomial time regardless of complexity assumptions.

Load-bearing premise

The NP-hardness result depends on the assumption that P ≠ NP, which is widely believed but not proven; however, the representation obstruction (Theorems 7 and 8) holds unconditionally, requiring no complexity-theoretic assumption.

Editorial extensions

If this is right

The output feedback stabilization problem is now known to be intractable in the worst case, closing a major open question in control theory listed by Blondel, Gevers, and Lindquist (1995).
Unless P = NP, any algorithm for output feedback stabilization requires exponential time in the worst case, and no pseudo-polynomial-time algorithm exists either.
Even if a stabilizing controller exists, the representation obstruction means that a polynomial-time algorithm cannot, in general, write down the controller in its standard dense encoding.
The result immediately extends to discrete-time systems via the Cayley transform, with the same strong NP-hardness guarantee.
The construction uses only integer entries of polynomial magnitude, so the hardness is genuine and not an artifact of large input encoding.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The representation obstruction suggests that output feedback stabilization may not belong to NP: any certificate of stabilizability would need to encode the controller itself, which may require exponentially many bits. The problem lies in PSPACE.
The proof technique—using widely spaced eigenvalues to decouple blocks and encoding a SAT instance into the (1,1) entries of diagonal blocks—may be applicable to other matrix feasibility problems where an affine family of matrices must contain a Hurwitz or Schur matrix.
Practitioners may now focus on tractable subclasses (e.g., state feedback, fixed-order controllers, or systems with additional structure) or on approximation and heuristic methods, since the general problem is provably hard.
The bijection between continuous and discrete time controllers via the Cayley transform is shown to preserve polynomial-size denumerators, allowing the strong hardness result to transfer without inflating denominators exponentially.

Original 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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,517 input tokens.

What the abstract itself states, as probabilities: claims first 0.12 · states limitation 0.39 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.19 · compares with prior results 0.13 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	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.	result 0.98	0.93	0.95	asserted 1.00
s1	This settles one of the best-known open problems in control theory.	interpretation 0.95	0.47	0.08	asserted 1.00
s2	The result holds in both continuous and discrete time.	result 0.95	0.72	0.05	asserted 1.00
s3	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.	result 0.88	0.94	0.15	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.