Reachability and Mortality for Two-Dimensional RHPCD Systems Are co-NP-hard

Reachability and mortality are fundamental problems in the study of hybrid dynamical systems. Reachability investigates whether a system can evolve from an initial state to a designated target state, while mortality asks whether the system inevitably halts or reaches a deadlock state under its given dynamics. In this work, we study these problems for two-dimensional restricted hierarchical piecewise constant derivative systems (2-RHPCD), a class characterised by a hierarchical structure and piecewise-constant dynamics. We prove that both reachability and mortality for 2-RHPCD systems are co-NP-hard. In particular, our result resolves the open question concerning the complexity of the mortality problem for 2-RHPCD systems.