[Topologists] AIM Seminar today

[Robert Ghrist]

Don't forget the Appied/Interdisc Mathematics Seminar:


  Applied/Interdisciplinary Mathematics Seminar
<http://torus.math.uiuc.edu/cal/math/cal?year=2006&month=03&day=06&interval=year&regexp=Applied%2fInterdisciplinary+Mathematics+Seminar&use=Find>
3:00 pm   in 3405 Siebel Center,  Monday, March 6, 2006

*P. Tosic* (UIUC Computer Science)
*On the Computational Complexity of Counting in Certain Classes of Sparse
Graph Automata*
Abstract: We study computational complexity of counting the fixed point
configurations (FPs), garden of Eden configurations (GEs), and predecessor
configurations in certain types of graph automata. We prove that both exact
and approximate counting of fixed points in Sequential and Synchronous
Dynamical Systems (SDSs and SyDSs, respectively) are computationally
intractable problems. This intractability is shown to hold even when each
node is required to update according to (i) a monotone Boolean function,
(ii) a symmetric Boolean function, or even (iii) a simple threshold function
that is both monotone and symmetric. We also show that the problems of
counting exactly the garden of Eden configurations (GEs), all transient
configurations, and all predecessors of an arbitrary configuration, are also
computationally intractable. Moreover, the hardness of the exact enumeration
of FPs and other types of configurations holds even in some severely
restricted cases, i.e., when the nodes of an SDS or SyDS use at most two
different Boolean functions from an appropriately restricted class of the
node update rules, and, additionally, when the underlying graphs are
constrained so that each node has only c = O(1) neighbors for small values
of c.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://graphics.cs.uiuc.edu/pipermail/topologists/attachments/20060306/6f35378d/attachment.html