Minimal reachability is hard to approximate
Files
Published version
Date
2017
Authors
Jadbabaie, Ali
Olshevsky, Alexander
Pappas, George J.
Tzoumas, Vasileios
Version
Published version
OA Version
Citation
Ali Jadbabaie, Alexander Olshevsky, George J Pappas, Vasileios Tzoumas. 2017. "Minimal Reachability is Hard To Approximate." IEEE Transactions on Automatic Control, https://doi.org/10.1109/TAC.2018.2836021
Abstract
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.
Description
License
© 2011 IEEE.