Moore
Le Jeudi 16 Septembre 1999 à 14h30
Salle de Conférences du LIX, École Polytechnique
Cris Moore
Santa Fe Institute
Chercheur invité à l'École Polytechnique
Computational Complexity in Physics and Cellular Automata
Résumé/Abstract :
Given the initial conditions of a cellular automaton (CA), how hard is it
to predict its state t time-steps in the future? This question is of
interest to anyone doing numerical experiments, but it can also be viewed
as a fundamental question about a system's dynamics. If a system is
highly contingent on its histroy, we will have to simulate it explicitly,
step-by-step; but if its dependences are in some way sparse, there may be
"short-cuts" that allow us to predict its final state without going
through all the history in between.
In fact, there are such short-cuts for certain cellular automata,
including nonlinear ones. For CA rules based on solvable groups, or on a
nice class of non-associative algebras, we can predict t steps in
O(log
t) time on a parallel computer. This pla
ces the prediction
problem for these systems in the class NC of efficient parallel
computation.
On the other hand, a number of CA rules of physical interest, such as
lattice gases, diffusion-limited aggregation, majority-voting rules
inspired by the Ising model of magnetism, and sandpiles, we can show that
the prediction problem is P-complete --- suggesting that explicit
simulation is probably necessary. For some of these, the two-dimensional
case remains an open question.