Minimal Reachability is Hard To Approximate
arXiv:1710.1024425 citationsh-index: 105
Originality Synthesis-oriented
AI Analysis
For control theorists and engineers, it establishes fundamental limits on the tractability of actuator placement in linear systems.
The paper proves that the problem of selecting actuated nodes in a linear dynamical system to enable state transfer is computationally hard to solve or approximate in polynomial or quasi-polynomial time, assuming standard complexity hypotheses.
In this note, we consider the problem of choosing which nodes of a linear dynamical system should be actuated so that the state transfer from the system's initial condition to a given final state is possible. Assuming a standard complexity hypothesis, we show that this problem cannot be efficiently solved or approximated in polynomial, or even quasi-polynomial, time.