Intractable Problems in Control Theory
Authors:
- Christos H. PapadimitriouCPChristos H. Papadimitriou
- John TsitsiklisJTJohn Tsitsiklis
- 1 July 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 24 (4) , 639-654
Abstract
This paper is an attempt to understand the apparent intractability of problems in decentralized decision-making, using the concepts and methods of computational complexity. 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 (the team decision problem in our particular example) can imply that there is no satisfactory (continuous) algorithm for the continuous version. To this end, we develop a theory of continuous algorithms and their complexity, and a quite general proof technique, which can prove interesting by themselves.Keywords
This publication has 10 references indexed in Scilit:
- On the complexity of decentralized decision making and detection problemsIEEE Transactions on Automatic Control, 1985
- Optimal causal coding - decoding problemsIEEE Transactions on Information Theory, 1983
- On the computational complexity of ordinary differential equationsInformation and Control, 1983
- Sparse sets in NP-P1983
- On the complexity of designing distributed protocolsInformation and Control, 1982
- The complexity of the generalized Lloyd - Max problem (Corresp.)IEEE Transactions on Information Theory, 1982
- Another look at the nonclassical information structure problemIEEE Transactions on Automatic Control, 1980
- On the determination of the optimal constant output feedback gains for linear multivariable systemsIEEE Transactions on Automatic Control, 1970
- A Counterexample in Stochastic Optimum ControlSIAM Journal on Control, 1968
- Team Decision ProblemsThe Annals of Mathematical Statistics, 1962