On the Complexity of Reachability and Mortality for Bounded Piecewise Affine Maps

Abstract

Reachability is a fundamental decision problem that arises across various domains, including program analysis, computational models like cellular automata, and finite- and infinite-state concurrent systems. Mortality, closely related to reachability, is another critical decision problem. This study focuses on the computational complexity of the reachability and mortality problems for two-dimensional hierarchical piecewise constant derivative systems (2-HPCD) and, consequently, for one-dimensional piecewise affine maps (1-PAM). Specifically, we consider the bounded variants of 2-HPCD and 1-PAM, as they are proven to be equivalent regarding their reachability and mortality properties. The proofs leverage the encoding of the simultaneous incongruences problem, a known NP-complete problem, into the reachability (alternatively, mortality) problem for 2-HPCD. The simultaneous incongruences problem has a solution if and only if the corresponding reachability (alternatively, mortality) problem for 2-HPCD does not. This establishes that the reachability and mortality problems are co-NP-hard for both bounded 2-HPCD and bounded 1-PAM.