strong np-hardness

Complexity of output feedback stabilization

Categories Control Applications, Semi-definite Programming Tags , ,

We show that unless \(\mathrm P=\mathrm{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 … Read more

Dynamic Spectrum Management: A Complete Complexity Characterization

Categories Applications - OR and Management Sciences, Global Optimization Theory, Telecommunications Tags , , ,

Consider a multi-user multi-carrier communication system where multiple users share multiple discrete subcarriers. To achieve high spectrum efficiency, the users in the system must choose their transmit power dynamically in response to fast channel fluctuations. Assuming perfect channel state information, two formulations for the spectrum management (power control) problem are considered in this paper: the … Read more