Reachability for piecewise affine systems is known to be un-decidable, starting from dimension 2. In this paper we investigate the exact complexity of several decidable variants of reachability and control questions for piecewise affine systems. We show in particular that the region to region bounded time versions leads to NP-complete or co-NP-complete problems, starting from dimension 2.
展开▼
