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.)