Computational complexity in systems and control

A problem in systems and control theory can be considered to be satisfactorily solved only if an algorithm is available with moderate computational requirements. For many problems, it may be unclear whether this is the case. Computational complexity theory can shed much light.

The subject is multifaceted and interesting in many different ways. It can help the practitioner in choosing problem formulations, and in calibrating expectations of what can be algorithmically accomplished. For the systems theorist or the applied mathematician, it raises a variety of challenging open problems that require a diverse set of tools from both discrete and continuous mathematics. Finally, for the theoretical computer scientist, the problems in systems and control theory provide the opportunity to relate abstractly defined complexity classes and specific problems of practical interest.

For a survey of the state of the art (as of 1999), and many open problems, see:

Shorter presentations of some results and open problems can be found in:

On the complexity of deciding stability properties of restricted classes of nonlinear systems:

Questions related to the stability or growth of products of matrices, taken from a finite set, but in an arbitrary order, are related to stability problems for time-varying linear systems. Such questions can be often hard to decide:

Recognizing convex polynomials

Markov decision theory

Open-loop control of Markov chains is NP-complete. The control of partially observable Markov chains (POMDPs) is PSPACE-complete:

Controlling queueing networks requires provably exponential time. Even though dynamic programming problems are solvable in polynomial time, the computational requirements become exponentially larger when a problem is "succintly" described: In fact, even stabilizing a queueing network while keeping expected delay polynomially small is hard: There are also results on dynamic programming on continuous state spaces:

Static output feedback with bounds on the feedback gains is a hard problem:

The complexity of supervisory control problems in the Ramadge-Wonham setting is essentially the same as for problems of controlling Markov chains:

Game theory

Distributed decision making

A discrete counterpart of Witsenhausen's counterexample in decentralized control is NP-complete. A connection is also made between discrete complexity theory and problems defined on continuous domains.