PaperlayerView exact revision on arXiv

Source-linked AI summary

On the NP-Hardness of Unconstrained Static Output Feedback Stabilization

Gal Barkai, Iman Shames

arXiv:2609.38728v1eess.SYcs.SY

TL;DR

Unconstrained static output feedback stabilization had remained open as a complexity question. The paper reduces Subset Sum to it using scalar blocks and a frequency-separated plant construction, and proves the stabilization problem NP-hard.

  • Problem

    Whether unconstrained static output feedback stabilization is NP-hard remained open, despite hardness results for related constrained problems.

    Source: §I · p. 1

  • Method

    The paper reduces Subset Sum by encoding discrete choices and a weighted-sum constraint in scalar blocks, then comparing local root counts for the coupled plant.

    Source: A. The continuous subset sum problem · p. 2, D. The plant family · p. 4, §IV · p. 6

  • Results

    Unconstrained static output feedback stabilization is NP-hard.

    Source: D. Correctness · p. 11

  • Takeaways & Limitations

    A polynomial-time reduction preserves YES and NO answers, establishing NP-hardness for unconstrained stabilization.

    Source: D. Correctness · p. 11

    The construction uses plant entries with exponential magnitudes, and it remains unknown whether hardness holds when their numerators and denominators are polynomially bounded.

    Source: §VI · p. 12

Abstract

from arXiv · show

In this paper we give a polynomial-time reduction from the Subset Sum Problem to unconstrained static output feedback stabilization, establishing its NP-hardness. The construction uses two scalar building blocks to impose approximate discrete choices and a weighted-sum constraint. Once the problem is encoded, we relate the stability of the $N+1$ decoupled loops encoding the problem to that of a coupled plant. This is accomplished by leveraging frequency separation via a band-pass transformation, and comparing the root counts of the true characteristic polynomial with that of the different blocks in different regions of the right half-plane. The construction then naturally bounds every stabilizing gain and gives explicit modulus-margin estimates, ensuring that the plant data have polynomial binary encoding length.

I. INTRODUCTION

The paper resolves the open question of whether unconstrained static output feedback stabilization is NP-hard by reducing Subset Sum to it. Its construction replaces discrete choices with gain intervals and a weighted-sum constraint, then builds scalar blocks that enforce those constraints through stability.

I. INTRODUCTION

  • The paper proves that unconstrained static output feedback stabilization is NP-hard, resolving a previously open complexity question.The problem asks whether a static gain can make a given linear time-invariant plant internally stable.Source: §I · p. 1

II. PROBLEM STATEMENTS AND THE CONTINUOUS RELAXATION

  • A polynomial-time reduction from Subset Sum must recover a solution from any stabilizing real gain because the feedback gain is unconstrained.The reduction maps YES and NO instances while keeping the rational plant data's encoding length polynomial.Source: §II · p. 2

A. The continuous subset sum problem

  • The continuous relaxation replaces each binary choice with a gain near 1 or 2 and constrains the weighted sum, with slack permitting exact rounding back.The stated rounding condition is δ + ϵΣ_i a_i < 1.Source: A. The continuous subset sum problem · p. 2

III. SCALAR BUILDING BLOCKS AND THE PLANT FAMILY

  • Two scalar blocks encode the relaxed constraints: one creates two narrow stabilizing-gain intervals, and the other constrains the weighted sum near the target.Frequency-separated copies of the first block are used in the plant construction.Source: §III · p. 2

A. The two-interval prototype

  • The two-interval prototype is constructed by interpolation at desired stability crossings; its unique rational coefficients are computable in polynomial time for rational ϵ.The prescribed crossings are verified to yield exactly the required stability intervals.Source: A. The two-interval prototype · p. 3

B. The summing block

The summing block restricts the weighted gain sum to a narrow interval around the target. A low-pass-to-band-pass transformation produces frequency-centered copies of the two-interval prototype while preserving their stability behavior.

B. The summing block

  • The summing block is Hurwitz exactly when the weighted gain sum W lies in (W* − δ, W* + δ).Its imaginary-axis crossings occur at the interval endpoints.Source: B. The summing block · p. 3

C. The band-pass transformation

  • The transformation is the low-pass-to-band-pass frequency map used to create the frequency-separated blocks in the plant.The map sends the open right and left half-planes to themselves and nonzero imaginary-axis points to the imaginary axis.Source: C. The band-pass transformation · pp. 3–4
  • The band-pass transformation maps the prototype into frequency-centered copies while preserving whether each scalar closed loop is Hurwitz.The transformation preserves the prototype's modulus margin as well.Source: C. The band-pass transformation · p. 4

D. The plant family

The plant combines frequency-separated copies of the two-interval prototype with a shared weighted summing block. Its state-space realization has 10N + 3 states, and rational parameter choices yield rational plant data of polynomial bit length.

D. The plant family

  • The plant is a parallel interconnection of N band-pass prototype copies centered at distinct frequencies, together with weighted copies of the shared summing block.The single-input plant has N outputs, and its feedback gain is a row vector.Source: Figure 1 · p. 4, D. The plant family · p. 4
  • The realization uses 10N + 3 states and makes closed-loop stability equivalent to the Hurwitz property of the constructed characteristic polynomial.The plant is formed from block-diagonal state dynamics, with the output matrix coupling each prototype block and the shared summing block to its output.Source: D. The plant family · p. 5
  • For rational construction parameters, the plant entries are rational and have polynomial bit length in those parameters, W*, and the Subset Sum weights.The realization builds on rational scalar-block coefficients and frequency parameters.Source: D. The plant family · p. 5

IV. COMPARISON, FREQUENCY SEPARATION AND LOCAL ROOT COUNTS

The section compares the coupled plant with one scalar loop at a time in separated right-half-plane regions, using root-count preservation to relate plant stability to the decoupled factors. When every scalar modulus margin exceeds the interaction bound, the plant and nominal system have matching right-half-plane root counts.

IV. COMPARISON, FREQUENCY SEPARATION AND LOCAL ROOT COUNTS

  • Pnom is Hurwitz exactly when its scalar gains satisfy the continuous-SSP constraints, which rounding converts to an SSP solution; conversely, each solution supplies gains.The converse uses gains 1 + x for an SSP solution x.Source: §IV · p. 5
  • Direct comparison with the nominal product can fail near a scalar crossing, where that product vanishes while a nonzero loop tail remains.Arbitrary stabilizing gains may approach crossing values, so the reverse direction needs a local comparison that does not require margins for every other factor.Source: §IV · pp. 5–6
  • The comparison uses Rouché’s theorem on each region boundary, bounding the perturbation by the sum of all loop terms other than the selected loop.Comparing Ptrue with (1 + Li)Dtot retains the block denominators and includes internal modes.Source: §IV · pp. 6–7
  • Separated center frequencies localize each block’s roots to its own comparison region, while off-band estimates bound the other loops’ combined contribution by T.The conditions separate consecutive bands and place the first band above the summing dynamics; the regions have disjoint interiors.Source: §IV · p. 6
  • On imaginary-axis boundary segments the scalar modulus margin controls the selected return difference; on circular arcs, decay provides the bound needed for local comparison.A margin greater than T, with T ≤ 1/4, supplies the required domination.Source: §IV · p. 6, Figure 4 · p. 7
  • For each region Ri whose selected margin mi exceeds T, Ptrue and the selected scalar factor have the same right-half-plane root count.Ptrue has no roots in the remaining region G.Source: §IV · p. 7
  • When every scalar margin exceeds T, Ptrue is Hurwitz if and only if all N+1 factors of Pnom are Hurwitz.Under the same condition, their right-half-plane root counts agree.Source: §IV · p. 7

V. THE REDUCTION

The reduction must make stability of the coupled plant enforce the scalar constraints encoding Subset Sum, despite unconstrained feedback gains. It bounds every stabilizing gain and chooses parameters so the reduction works in both directions.

V. THE REDUCTION

  • Frequency separation and root-count comparisons relate stability of the coupled plant to the scalar constraints encoded by the decoupled loops.The comparison requires bounded gains and weighted sum, sufficiently separated center frequencies, and coupling smaller than the scalar margins.Source: §V · pp. 7–8
  • The gain bounds needed for the reduction are derived from plant stability, not imposed as constraints on the SOFS instance.The construction first bounds the weighted sum W, then uses the prototype’s right-half-plane zero to bound every gain entry.Source: §V · p. 8
  • Parameter choices preserve enough slack for rounding, so exact gains in {1, 2} stabilize YES instances and any stabilizing gain yields an SSP solution.The plant is constructible in polynomial time and has polynomial bit length.Source: §V · p. 8

A. Enforcing bounds on stabilizing gains

The reduction first bounds the weighted sum W using necessary coefficient conditions, then bounds every individual gain using a right-half-plane zero of the band-pass prototype. These a priori bounds hold for any stabilizing gain.

A. Enforcing bounds on stabilizing gains

  • Positivity of the degree-1 and degree-(d−1) coefficients gives necessary bounds on W without restricting individual gains.The band-loop terms contribute to neither coefficient; the resulting bounds control the summing-loop contribution even if gain entries are large.Source: A. Enforcing bounds on stabilizing gains · p. 8
  • Coefficient positivity and the frequency conditions yield the necessary weighted-sum range −N d4 Bw < W < 2W* + 1 for stabilizing gains.These bounds let the later margin analysis work over a bounded set.Source: A. Enforcing bounds on stabilizing gains · p. 8
  • Near the prototype’s right-half-plane zero, a largest-magnitude band gain dominates when frequencies are sufficiently separated, forcing a right-half-plane root if it exceeds the cap.The proof localizes open-loop denominators near that zero and uses Rouché’s theorem to obtain a contradiction with Hurwitzness.Source: A. Enforcing bounds on stabilizing gains · pp. 8–9
  • If Ptrue is Hurwitz, Proposition V.2 bounds every gain entry by κ* under its frequency and coupling conditions.The proposition requires Assumption IV.1 for (κ, w) = (1, w̄) and TGB ≤ μ/4; it concludes maxi |ki| ≤ κ*.Source: A. Enforcing bounds on stabilizing gains · p. 8

B. Explicit modulus margin bounds

Explicit lower bounds on scalar modulus margins make it possible to choose coupling and frequencies quantitatively. The bounds depend on distance from the crossing gains, where the margins vanish.

B. Explicit modulus margin bounds

  • Lemma V.3 establishes the prototype margin by separating low, intermediate, and high frequencies and bounding the return difference in each range.The proof rules out simultaneous small values of f and h using a resultant and a bounded Bézout identity; near zero it uses the constant term, while high-frequency decay suffices beyond Y.Source: B. Explicit modulus margin bounds · pp. 9–10
  • For every real g with |g| ≤ κ and distance τ > 0 from {1−ϵ, 1+ϵ, 2−ϵ, 2+ϵ}, mb(g) ≥ Mb(min{τ, 1}); for every real W with |W| ≤ w and distance τW > 0 from {W*−δ, W*+δ}, ms(W) ≥ Ms(min{τW, 1}).Source: B. Explicit modulus margin bounds · p. 9
  • The resulting prototype margin lower bound is Mb(τ̂)^2, with the third frequency-range estimate determining the minimum.The proof states that this entry is the smallest after using the coefficient and frequency bounds.Source: B. Explicit modulus margin bounds · p. 10
  • The summing-block margin uses the same three frequency ranges, with elimination yielding a lower bound at intermediate frequencies.The proof combines a constant-term estimate near zero with decay at high frequencies.Source: B. Explicit modulus margin bounds · p. 10

C. Parameter choice

The parameter choice fixes frequency separation, crossing neighborhoods, and margins as functions of the SSP instance. It ensures the gain bounds and small-coupling conditions required by the reduction.

C. Parameter choice

  • The definition selects crossing neighborhoods and ω1 using the explicit margin bounds, then realizes the plant with those parameters.The parameter choice is made from the SSP instance.Source: C. Parameter choice · p. 10
  • The parameter choice makes the hypotheses of the a priori gain bound hold and places the relevant scalar margins above m̄.It ensures mb(1), mb(2), and ms(W*) are at least m̄.Source: C. Parameter choice · p. 10
  • The chosen frequencies make the coupling T smaller than both m̄ and 1/4.This choice uses the gain bounds (κ*, w̄) and a frequency ω1 selected above the stated threshold.Source: C. Parameter choice · p. 10
  • The margins at gains 1 and 2 and at W* are sufficient because these targets lie at distances ε and δ from their respective crossings.The proof uses θ ≤ ε and θW ≤ δ together with monotonicity of Mb and Ms.Source: C. Parameter choice · p. 10

D. Correctness

The correctness proof shows that a Subset Sum YES instance yields a stabilizing gain and that any stabilizing gain implies a YES instance. The resulting polynomial-time reduction establishes NP-hardness.

D. Correctness

  • A Subset Sum YES instance yields a gain with entries in {1, 2} that stabilizes the constructed plant.The selected gains satisfy the target weighted sum, and the corresponding true characteristic polynomial is Hurwitz.Source: D. Correctness · p. 11
  • Any stabilizing real gain satisfies enlarged interval and weighted-sum constraints that can be rounded to a Subset Sum solution.The proof first bounds the gain entries and weighted sum, then applies the rounding lemma.Source: D. Correctness · p. 11
  • The two directions give a polynomial-time map preserving YES and NO answers, with plant data of polynomial bit length.Theorem V.8 establishes the reduction; its size analysis shows that the plant parameters can be computed with polynomial encoding length.Source: D. Correctness · p. 11
  • Because Subset Sum is NP-complete, the reduction proves that unconstrained static output feedback stabilization is NP-hard.The argument uses a Karp reduction and does not establish membership in NP.Source: D. Correctness · p. 11

VI. CONCLUDING REMARKS

The paper concludes that unconstrained SOFS is NP-hard and lies in PSPACE, while identifying open complexity questions and disclosing the use of AI tools for review and writing assistance.

VI. CONCLUDING REMARKS

  • The reduction also yields NP-hardness for plants with N inputs and one output by transposing the constructed plant.Transposition preserves the closed-loop eigenvalues and bijectively maps the gain sets.Source: §VI · p. 11
  • Unconstrained SOFS lies in PSPACE because its stability condition can be expressed as a polynomial-length existential sentence over the reals.The sentence uses a Lyapunov matrix and triangular factors to encode positive definiteness.Source: §VI · pp. 11–12
  • Strong NP-hardness, membership in NP, and completeness for the existential theory of the reals remain open; the construction uses exponentially large rational magnitudes.The authors also specify additional block behavior and error control needed for a hardness proof for the existential theory of the reals.Source: §VI · p. 12

DECLARATION ON GENERATIVE AI

  • The authors report using ChatGPT 5.6 and Claude Opus 5 for adversarial review and writing assistance, but not for idea generation or proof writing.They state that the authors assume responsibility for the paper's content.Source: DECLARATION ON GENERATIVE AI · p. 12

APPENDIX A EXPLICIT CONSTRUCTION OF A PROTOTYPE Hb

Appendix A constructs the scalar prototype by rational interpolation, then verifies its imaginary-axis crossings, stabilizing intervals, and coefficient and margin bounds.

APPENDIX A EXPLICIT CONSTRUCTION OF A PROTOTYPE Hb

  • The interpolation conditions form a rational linear system with a unique solution for every ϵ in (0, 1/8], enabling effective construction of Hb.Its coefficient matrix has nonzero determinant on that interval, and rational ϵ gives coefficients with polynomial bit length.Source: Appendix A · p. 12
  • The prototype polynomial has imaginary-axis roots exactly at gains 1 − ϵ, 1 + ϵ, 2 − ϵ, and 2 + ϵ.The nonzero-frequency crossings occur at the three gains 1 + ϵ, 2 − ϵ, and 2 + ϵ; the remaining crossing is at zero.Source: Appendix A · p. 12
  • The only stabilizing gain intervals are (1 − ϵ, 1 + ϵ) and (2 − ϵ, 2 + ϵ).Routh's criterion checks one gain in each component between the four imaginary-axis crossings.Source: Appendix A · p. 13
  • At gain zero, the denominator polynomial has exactly one open-right-half-plane root, which is real.The Routh sign sequence gives one such root, and conjugate pairing makes it real.Source: Appendix A · p. 13
  • The numerator polynomial has p = 3 as its only root in the closed right half-plane, and that root is simple.Its quadratic factor is Hurwitz because both coefficients are positive.Source: Appendix A · p. 13
  • The appendix supplies coefficient bounds and a lower-bound argument for Hb on the specified annulus around p = 3.The coefficient estimates include 0 < n2 ≤ 16/7, 0 < n1 ≤ 4, and 0 < n0 ≤ 24/7; the annulus argument uses the roots of the quadratic numerator factor.Source: Appendix A · p. 13

APPENDIX B ESTIMATES FOR FREQUENCY SEPARATION

Appendix B bounds the scalar blocks' decay away from their frequency bands and locates their roots, supporting comparisons between decoupled blocks and the coupled plant.

APPENDIX B ESTIMATES FOR FREQUENCY SEPARATION

  • Away from the assigned frequency bands, the prototype and summing transfer functions decay as |Hb(p)| ≤ 4/|p|^2 and |Hsum(s)| ≤ 4/|s|.The appendix also gives a bound of 8/ω1 for the summing term when |s| ≥ ω1/2.Source: Appendix B · p. 14
  • For bounded gains, each band block's roots lie in its frequency annulus, while the summing block's roots lie within radius ω1/4.The band annulus is {2ωi/3 ≤ |s| ≤ 3ωi/2}, and the summing-block bound holds for |W| ≤ w.Source: Appendix B · p. 14
  • The stated comparison estimates assume bounded gain entries and a bounded weighted sum.Under Assumption IV.1, the bounds apply when |kj| ≤ κ for all j and |W| ≤ w.Source: Appendix B · p. 14
  • On comparison boundaries, frequency spacing places nonmatching band terms and the summing term in the regions where their decay bounds apply.The boundary estimates use the separated frequencies to control contributions from the other blocks.Source: Appendix B · p. 14
Loading 2609.38728v1…