pipette
ESEspañol

On the NP-Hardness of Unconstrained Static Output Feedback Stabilization

Gal Barkai, Iman Shames

Preprint

In the authors' words

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

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.