A survey of computational complexity results in systems and control

By Vincent D. Blondel, John N. Tsitsiklis. 2000

816 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Deep learning in neural networks: An overview (2014, background): “For example, an answer to the famous question of whether P = NP (Cook, 1971; Levin, 1973b) would also set limits for what is achievable by general RL. Comparemore specific limitations, e.g., Blondel and Tsitsiklis (2000), Madani, Hanks, and Condon (2003) and Vlassis, Littman, and Barber (2012).”
LMI stability conditions for uncertain rational nonlinear systems (2014, background): “In this area, it is important to emphasize that potentially interesting methods found in the classical literature are of difficult numerical solution [2, 3], and sufficient conditions that are not too conservative are of great interest if they can be numerically tested in an efficient way.”
A Survey of Distributed Optimization and Control Algorithms for Electric Power Systems (2017, background): “It has long been known that this problem is computationally hard to solve and, in particular, NP-hard in the worst case [145]–[147].”
The boundedness of all products of a pair of matrices is undecidable (2000, background): “From this it follows that the problems of deciding whether ( )61 or whether ( )¡ 1 are NP-hard; see [20,10], as well as [9] for other relevant results; see also [4] for a general discussion.”
Lyapunov Design for Safe Reinforcement Learning (2003, background): “(See Blondel and Tsitsiklis, 2000, for a survey of complexity results from a control theory perspective.”
Corrigendum/addendum to: Sets of matrices all infinite products of which converge (2001, neutral): “Further results concerning effective computability and computational difficulty of such stability questions, including NP-completeness results, were obtained in [17–19,33,35] and surveyed in Blondel and Tsitsiklis [5].”
A Characterization of Convex Problems in Decentralized Control$^ast$ (2005, background): “In fact, certain cases have been shown to be intractable [ 3 ], [11].”
Approximation of the joint spectral radius using sum of squares (2007, methodology): “We refer the reader to the survey [BT00b, § 3.5] for further results and references on the computational complexity of the joint spectral radius.”
Planning algorithms (2006, background): “For the computational complexity of control problems, see [116, 769].”
Piecewise Linear Control Systems (2003, background): “Many analysis problems, even for mildly nonlinear systems, have been shown to be intractable or even impossible to solve by computations [18].”
The scenario approach to robust control design (2006, background): “the NP-hardness of several worst-case design problems are for instance found in [10], [13], [36].”
Stability Criteria for Switched and Hybrid Systems (2007, background): “…autonomous switched nonlinear system ẋ(t) = f(x, t), f(x, t) ∈ {f1(x), . . . , fm(x)}, t ≥ 0,(5.3) where each mode, fi, is assumed to be globally Lipschitz continuous and exponentially stable, and where the switching strategy is chosen in such a way that there are finite switches in finite time.”
A Tour of Reinforcement Learning: The View from Continuous Control (2018, background): “In general, this problem gets into very old intractability issues of nonlinear output feedback in control [17] and partially observed Markov decision processes in reinforcement learning [57].”