## 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.

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.

Original language | English |
---|---|

Pages | 1-13 |

Number of pages | 13 |

Publication status | Accepted/In press - 30 Jul 2024 |

Event | Reachability Problems - Vienna, Austria Duration: 25 Sept 2024 → 27 Sept 2024 |

### Conference

Conference | Reachability Problems |
---|---|

Country/Territory | Austria |

City | Vienna |

Period | 25/09/24 → 27/09/24 |