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 are co-NP-hard for bounded \(2\) -RHPCD systems. In particular, our result resolves the open question posed in [4] concerning the complexity of the mortality problem for \(2\) -RHPCD systems.