Intractable problems in control theory

This paper is a study of the apparent intractability of problems in decentralized decision-making, using the concepts and methods of Complexity Theory. We first establish that the discrete version of an important paradigm for this area, proposed by Witsenhausen, is NP-complete, thus explaining the failures reported in the literature to attack it computationally. In the rest of the paper we show that the computational intractability of the discrete version of a control problem can imply that there are no satisfactory (continuous) algorithms for the continuous version. To this effect, we develop a theory of continuous algorithms and their complexity, and an analytical methodology, which can prove quite interesting by themselves.