Hard questions about simple finite dynamical systems

Winfried Just
Department of Mathematics, Ohio University

(May 25, 2006 10:30 AM - 11:30 AM)

Hard questions about simple finite dynamical systems

Abstract

A Boolean dynamical system is a dynamical system whose state space consists of vectors of fixed finite length of Boolean values 0 and 1. Such systems have important applications in mathematical biology as models of gene regulatory networks. In studying these models, one would like to have an efficient algorithm for deducing the dynamical properties of the system from the formula for the updating function. In particular, one would like to know if all attractors of the system are steady states. Efficient algorithms for this problem are known if the updating function is linear or each of its components is a monomial. In this talk we will see that if the set of permissible updating functions is only slightly broadened, the problem becomes computationally intractable, more precisely, NP-hard.

In this talk we will present Boolean dynamical systems as models of gene regulatory networks and will review the basics of NP-hardness. Then we will state our main results and illustrate the technique of proving NP-hardness of a given combinatorial problem with one of our proofs.