Year: 2017 | |

1/13 | [elc] ELCセミナー（Prof. Mitsunori Ogihara) |

Place : CELC Seminar room | |

title: The Complexity of the Predecessor and Garden-of-Eden Problems of Synchronous Boolean Finite Dynamical Systems date: January 13rd, 2017, 11:00- place: CELC Seminar room presenter: Mitsunori Ogihara, University of Miami Absrtact: The boolean finite dynamical system is the most stringent form of dynamical systems in which the system size is fixed, the state of each object in the system is boolean, and the state update occurs synchornously for all the objects in the system. The action in one step of a system can be viewed as a function from a set of some n boolean variables to itself, and thus, the reversing action as a partial one-to-many function of that set. This talk considers the complexity of two problems related to the reversibility: (1) The t-Predecessor Problem: given a configuration and t >= 1, is it possible to reverse the process from the configuration successfully t times? (2) The t-Garden-of-Eden Problem: given a configuration and t >= 1, is it possible to reverse the process from the configuration successfully t times to arrive at a configure with no inverse? In this talk, I will present some results to pinpoint the complexity of these problems for various sets of function basis. (a) If the available function is pure bit transferring (i.e., assign the value of one state to another), both problems are in AC^0. (b) If the available function is the bounded-fan-in OR (or the bounded-fan-in AND), both problems are in AC^0. (c) If the available function is the unbounded-fan-in OR (or the unbounded-fan-in AND), the t-Predecessor Problem is in AC^0 and the t-Garden-of-Eden Problem is NP-complete for all constants t. (d) If the functions are chosen from the 2-fan-in OR and the 2-fan-in AND, the 1-Predecessor Problem is NL-complete and the 1-Garden-of-Eden Problem is NL-hard and is in NP. (e) If the functions are chosen from the 3-fan-in OR and the 2-fan-in AND (or from the 2-fan-in OR and the 3-fan-in AND), then the t-Predecessor Problem is NP-complete and the t-Garden-Of-Eden Problem is Sigma^p_2-complete. This is joint wirk with Akinori Kawachi (Kochi U.) and Kei Uchizawa (Yamagata U.) |

horiyama@al.ics.saitama-u.ac.jp