ELC Seminar 
Date: October 13(Tue), 2015
Time: 11:00~

Speaker: Prof. Mitsunori Ogihara （University of Miami）
Title: Complexity of Synchronous Boolean Finite Dynamical Systems
Abstract: The finite dynamical system is a system consisting of some finite
number of objects that take upon a value from some domain as a state, where
after initialization the states of the objects are updated based upon the
states of the other objects and themselves according to a certain update
schedule.  The synchrnous boolean finite dynamical system (synchronous BFDS,
for short) is its subclass in which the states are boolean and the state
update takes place in discrete time and at the same on all objects.

This talk is concerned with some problems regarding the behavior of
synchronous BFDS in which the state update functions are chosen from
a predetermined finite basis of boolean functions, in particular, the
problem of deciding convergence, the problem of calculating the cycle
length, and the problem of testing whether paths originating from two
configurations intersect.  I will show that:
. The three problems are each PSPACE-complete if the function basis can
  generate two out of { AND, OR, NOT }.
. If the basis is AND-only, OR-only, XOR-only, or XOR+NXOR only, then
  convergence is polynomial time solvable, the intersection problem is in
  UP, the cycle length problem is in UP-cap-coUP.
Also, I will show that the intersection problem is randomized polynomial
time reducible to the Minimum Circuit Size Problem.

This is joint work with Kei Uchizawa