Intractable Problems in Control Theory
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.
- The computational complexity of decentralized discrete-event control problems
- On the Computational Complexity of Stochastic Controller Optimization in POMDPs
- A survey of computational complexity results in systems and control
- The complexity of deciding controllability
- On the complexity of decentralized decision making and detection problems
- Some complexity problems on single input double output controllers
- There exists a linear problem with infinite combinatory complexity
- Decentralized decision-making in a large team with local information.
- Dynamic focal points in \(N\)-person coordination games
- Competitive distributed decision-making
- Geometry of information structures, strategic measures and associated stochastic control topologies
- Regularized stochastic team problems
- Stochastic algorithms for robustness of control performances
- Control design for autonomous vehicles: a dynamic optimization perspective
- On the complexity of decentralized decision making and detection problems
- scientific article; zbMATH DE number 1241686 (Why is no real title available?)
- Overview of complexity and decidability results for three classes of elementary nonlinear systems
- The computational complexity of decentralized discrete-event control problems
- Connectivity properties of the set of stabilizing static decentralized controllers
- An Approximation Algorithm for the Discrete Team Decision Problem
- Decentralised output-feedback LQG control with one-step communication delay
- A sub-optimal algorithm to synthesize control laws for a network of dynamic agents
- A survey of computational complexity results in systems and control
- New insights into Witsenhausen's counterexample
- Optimal memoryless control in Gaussian noise: a simple counterexample
- Controlling loosely cooperating processes
- Simultaneous design of measurement and control strategies for stochastic systems with feedback
- The complexity of deciding controllability
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)