IEEE Transactions on Automatic Control, Vol.64, No.2, 783-789, 2019
Minimal Reachability is Hard To Approximate
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.
Keywords:Approximation algorithms;computational complexity;controllability;(non-)submodularity;sparse actuator placement