Minimal Reachability is Hard To Approximate
Ali Jadbabaie, Alexander Olshevsky, George J. Pappas, Vasileios Tzoumas · IEEE Transactions on Automatic Control · 2018
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.