Complexity of Systems and Control

Theory Problems

P.W. Goldberg  C.T. Abdallah and G.L. Heileman^{1}
ICS Group  ICS Group
Dpt. of Computer Science  Dpt. of Electr. & Comp. Engineering
The University of New Mexico  The University of New Mexico
Albuquerque, NM 87131-1356  Albuquerque, NM 87131-1356

Abstract

Recently, reserach has been conducted to address the computational difficulty associated with many control and systems problems. This paper will review the state-of-the-art in this area. In particular, we study the problem of using decoupled static output feedback to control linear, time-invariant (LTI) systems. We use complexity-theoretic techniques to show that the problem of determining whether an LTI system can be made stable using decoupled static output feedback is an NP-hard problem, implying that an unreasonable amount of time may be needed to find the desired feedback parameters in large LTI systems. Specifically, under the strongly held assumption that P does not equal NP, these results demonstrate that a polynomial time (in the order of the LTI system) algorithm does not exist for solving the decoupled static output feedback problem.

1The research of C. Abdallah and G. Heileman was supported by Boeing Computer Services under contract W-300445.