Predecessor existence problems for finite discrete dynamical systems

We study the predecessor existence problem for finite discrete dynamical systems. Given a finite discrete dynamical system S and a configuration C, the Predecessor existence (or Pre) problem is to determine whether there is a configuration C′ such that S has a transition from C′ to C. In addition to the decision version, we also study the following variants: the #-Predecessor existence (or #Pre) problem–counting the number of predecessors, the Unique-Predecessor existence (or UPre) problem–deciding whether there is a unique predecessor and the Ambiguous-Predecessor existence (or APre) problem–given a configuration C and a predecessor C′ of C, deciding whether there is a different predecessor C″ of C. General techniques are presented for simultaneously characterizing the computational complexity of the Pre problem and its three variants. Our hardness results are based on the concept of simultaneous reductions: single transformations that can be used to simultaneously prove the hardness of the different variants of the Pre problem for their respective complexity classes. Our easiness results are based on dynamic programming and they extend the previous results on Pre problem for one-dimensional cellular automata. The hardness results together with the easiness results provide a tight separation between easy and hard instances. Further, the results imply similar bounds for other classes of finite discrete dynamical systems including discrete Hopfield and recurrent neural networks, concurrent state machines, systolic networks and one- and two-dimensional cellular automata. Our results extend the earlier results of Green, Sutner and Orponen on the complexity of the predecessor existence problem and its variants.