Intractable Problems in Control Theory

From MaRDI portal





This paper deals with the computational complexity of some nonclassical both discrete and continuous control problems, and with the relationship between the discrete and continuous version of a problem. The authors focus their attention on the team decision problem and the Witsenhausen stochastic decentralized control problem. The discrete team decision problem is known to be NP (nondeterministic polynomial)-complete. It is proved that the discrete version of the Witsenhausen problem is also NP- complete. Complexity of continuous problems depends on the accuracy of the solution, so that the relevant definitions are given in the paper. Also for the continuous version of the team decision problem suitable smoothness hypotheses are made that insure the existence of solutions. The other main result of the paper consists essentially in showing that the conjecture that \(P\neq NP\) is equivalent to the fact that, with respect to various definitions, the solution of the continuous team decision problem is not computable in polynomial time. A similar result is claimed to be provable for the continuous version of the Witsenhausen problem, relaxing the assumption of normality of the underlying random variables. In sum the main merits of the paper consist in collocating in the complexity scale some problems of decentralized decision making, both in discrete and continuous version, and in using a method of proof, that connects the two versions and that could be exploited to obtain similar results for other continuous problems not examined in the paper.




Cited in
(23)








This page was built for publication: Intractable Problems in Control Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3741336)