Predecessor existence problems for finite discrete dynamical systems

• Published in: Theoretical computer science 2007-10, Vol.386 (1), p.3-37
• Main Authors: Barrett, Chris, Hunt, Harry B., Marathe, Madhav V., Ravi, S.S., Rosenkrantz, Daniel J., Stearns, Richard E., Thakur, Mayur
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Cellular automata; Combinatorics; Combinatorics. Ordered structures; Computational complexity; Computer science; control theory; systems; Data flow analysis; Designs and configurations; Discrete dynamical systems; Exact sciences and technology; Global analysis, analysis on manifolds; Mathematics; Miscellaneous; Predecessor existence; Sciences and techniques of general use; Software and hardware verification; Theoretical computing; Topology. Manifolds and cell complexes. Global analysis and analysis on manifolds
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2007.04.026

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.