CS Paper Radar

On the NP-Hardness of Unconstrained Static Output Feedback Stabilization

Gal Barkai, Iman Shames

eess.SY ·submitted 2026-09-30 01:03 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Complexity of Output Feedback Stabilization

cs.CC math.OCeess.SY ·2026-09-17 ·Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang
similarity 0.60
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.

0.41

A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem over Networks via Output Feedback

eess.SY math.OC ·2026-10-15 ·Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte, Claudio Altafini
similarity 0.57
Abstract · MATLAB functions implementing the results presented in this article are available in the GitLab repository: https://gitlab.liu.se/lucle71/no…

For networked systems, we propose a polynomial-time algorithm for solving the minimal input/output node cardinality disturbance decoupling problem via output feedback. The algorithm computes an optimal solution, namely, a pair of minimum-cardinality sets of control input and measurement output nodes that achieve disturbance decoupling, by solving a min-cut/max-flow problem on an extended network.

0.28

Minimal Experiments for Robust Stabilization: Information, Spectral Geometry, and Duration

eess.SY math.OC ·2026-10-01 ·Alexey Peregudin, Ngoc Tuan Dinh
similarity 0.51
Abstract · 12 pages, 1 table. Submitted to IEEE Transactions on Automatic Control

On broad classes of linear systems, the shortest experiments are almost as good as the best possible ones. For $n$ states and $m$ inputs, the shortest input sequences that support robust data-driven stabilization of every controllable plant have $mn+1$ steps with exact states and $m(n+1)$ with noisy states. We show that, when the spectral radius is bounded and the spectrum is well separated near the unit circle, these sequences tolerate a fixed fraction of the error level achievable by any experiment, even one designed with full plant knowledge and allowed to use any finite duration. This constant-factor comparison can fail for slowly actuated systems. For $A=I+hG$ with controllability depth $ν\ge2$, short experiments lose a factor of order $h^{ν-1}$, and duration of order $1/h$ is both necessary and sufficient to recover a fixed fraction of the optimal tolerance.

0.56

Hardness of integer linear feasibility with cyclic support

cs.DM math.OC ·2026-11-05 ·Marco Di Summa
theory similarity 0.50
Abstract

We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No variable bounds are supplied separately from the system. For systems in which each inequality involves at most two variables, this strengthens known hardness results by restricting all numerical data to fixed finite sets. For systems in which each variable occurs in at most two inequalities, this establishes, to the best of our knowledge, the first $NP$-hardness result for feasibility. We also give negative answers, unless $P=NP$, to questions on polynomial-time solvability of integer programs with bounded coefficients and bounded totally $Δ$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.

0.24

Exact Noise Limits for Bounded Scalar Stabilization Experiments

eess.SY math.OC ·2026-09-30 ·Alexey Peregudin, Ngoc Tuan Dinh
similarity 0.50
Abstract · 6 pages, 1 figure. Submitted to the American Control Conference (ACC)

How much unknown process noise can a bounded experiment tolerate while still establishing that the plant can be stabilized? We answer this question for scalar discrete-time systems with bounded inputs, exact state measurements, and a disturbance-energy budget proportional to the experiment length. We distinguish individual stabilizability of every consistent model, stabilization by one common gain, and a common quadratic certificate. We determine their exact noise ceilings for every drift. The last two requirements coincide; individual stabilizability generally tolerates more noise. Bounded periodic inputs approach the ceilings, while adversarial disturbances prevent their attainment. We also determine the long-horizon limits. For unstable plants, a short experiment can establish individual stabilizability at noise levels where every sufficiently long experiment fails. The same obstruction yields upper bounds for multidimensional systems with real eigenvalues. Input design may use plant knowledge, but certification uses only the recorded data and noise bound. The results therefore provide fundamental robustness benchmarks for unknown-plant designs.

0.41

Exact Characterization of Admissible Bandwidths for Linear Disturbance Observers

eess.SY ·2026-10-22 ·Hamin Chang, Hyuntae Kim
similarity 0.49
Abstract · 5 pages, 1 figure

This paper characterizes the entire set of admissible Q-filter bandwidths, equivalently parameterized by the time constant $τ$, that guarantee robust internal stability of a linear disturbance observer (DOB) under parametric plant uncertainties. Classical small-$τ$ stability results provide a rigorous foundation for Q-filter bandwidth design. Building on this foundation, we formulate the $τ$-dependent robust internal-stability problem as a semialgebraic feasibility problem in bivariate polynomials and prove that the complete admissible set is a finite union of open intervals under the standing assumptions. A constructive procedure with exact membership tests recovers all stabilizing intervals. A numerical example with an uncertain plant family containing non-minimum-phase members illustrates a disconnected admissible set.

0.33

Constrained Sparsest Input Selection for Structural Controllability is NP-Hard

eess.SY ·2026-10-22 ·Yuan Zhang, Jintao Zhang, Yun Feng
similarity 0.49
Abstract · 6 pages, 1 figure

We study the problem of selecting the fewest admissible input--state links that make a structured linear system structurally controllable. This objective counts nonzero entries from prescribed positions of the input matrix and is different from minimizing its number of nonzero columns. Prior work gives polynomial-time algorithms for several restricted cases, including single or dedicated inputs and prescribed input patterns satisfying additional graph-theoretic conditions. We give a polynomial-time reduction from perfect three-dimensional matching, establishing for the first time that the decision problem is NP-complete and the optimization problem is NP-hard. A refinement of the reduction yields an exact optimum relation and shows that the problem is APX-hard. An example also exhibits a strict integrality gap for the natural linear programming relaxation.

0.24

Vector Balancing in Polynomial Time

cs.DS math.CO ·2026-09-20 ·Shengtao Guo, Ethan X. Fang, Junwei Lu
hot directionhighly cited similarity 0.49
Abstract · 23 pages, no figures

The Komlós problem asks for signs $\varepsilon\in\{-1,1\}^n$ with $\|A\varepsilon\|_\infty$ bounded by an absolute constant whenever the columns of $A\in\mathbb R^{m\times n}$ have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our deterministic algorithm achieves discrepancy at most $8272$. As a consequence, we obtain a deterministic $O(\sqrt t)$-discrepancy algorithm for the Beck-Fiala problem on set systems in which each element belongs to at most $t$ sets. Our algorithm rounds a fractional coloring while keeping the row sums bounded. Its key idea is to keep the number of nearly tight row constraints small relative to the number of active coordinates. We achieve this through a spectral bound based on a weighted Gram matrix of squared row entries. We maintain the bound using a cubic spectral potential and negative-curvature updates that satisfy the required linear constraints.

0.57