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:
V.D. Blondel and J. N. Tsitsiklis, "Overview of complexity and decidability results for three classes of elementary nonlinear systems", in Learning, Control and Hybrid Systems, Y. Yamamoto and S. Hara (Eds), Springer Verlag, Heidelberg, 1998, 46-58.
On the complexity of deciding stability properties of restricted classes of nonlinear systems:
V. D. Blondel, O. Bournez, P. Koiran, C. H. Papadimitriou, and J. N. Tsitsiklis, "Deciding stability and mortality of piecewise affine systems", Theoretical Computer Science, Vol. 255, No. 1-2, pp. 687-696, 2001.
V. D. Blondel, and J. N. Tsitsiklis, "Complexity of Stability and Controllability of Elementary Hybrid Systems", Automatica, Vol. 35, No. 3, March 1999.
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:
V. D. Blondel and J. N. Tsitsiklis, "The boundedness of all products of a pair of matrices is undecidable", Systems and Control Letters, Vol. 41, No. 2, pp.135-140, 2000.
J. N. Tsitsiklis and V. D. Blondel, "The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate", Mathematics of Control, Signals and Systems, Vol. 10, No. 1, 1997, pp. 31-40; correction in Vol. 10, No. 4, p. 381.
V. D. Blondel and J. N. Tsitsiklis, "When is a Pair of Matrices Mortal?", Information Processing Letters , Vol. 63, 1997, pp. 283-286.
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:
J. N. Tsitsiklis, "NP-Hardness of Checking the Unichain Condition in Average Cost MDPs," Operations Research Letters, Vol. 35, No. 3, May 2007, pp. 319-323.
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
D.E. Knuth, C.H. Papadimitriou, J.N. Tsitsiklis, "A Note on Strategy Elimination in Bimatrix Games", Operations Research Letters, Vol. 7, No. 3, 1988, pp. 103-107.
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.
J.N. Tsitsiklis and M. Athans, "On the Complexity of Decentralized Decision Making and Detection Problems", IEEE Transactions on Automatic Control, Vol. 30, No.5, 1985, pp. 440-446.
C.H. Papadimitriou and J.N. Tsitsiklis, "On the Complexity of Designing Distributed Protocols", Information and Control, Vol. 53, No. 3, 1982, pp. 211-218.