Publicación:

Problemas algorítmicos asociados al modelo Abeliano pilas de arena

Resumen

El modelo abeliano pilas de arena es un sistema dinámico discreto (un autómata celular) el cual podría llegar a representar fenómenos de la naturaleza cuya dinámica es disipativa. El modelo abeliano pilas de arena puede ser definido y estudiado sobre grafos arbitrarios pero el caso que más interés ha despertado es el de las grillas unidimiensionales, bidimensionales y tridimensionales, dado que estas son los modelos canónicos discretos del espacio euclidiano. Parte del interés que suscita el modelo se debe a que este parece exhibir la propiedad de auto-organización crítica, la cual estipula que el sistema converge espontáneamente a estados críticos. Este trabajo es en general un estudio de la complejidad computacional de algunos problemas algorítmicos asociados al modelo abeliano pilas de arena y está compuesto por cinco capítulos; en el primero se define el modelo y se muestran algunas características importantes acerca de éste mismo, en el segundo capítulo se introducen algunos problemas algorítmicos, en particular, el problema de la predicción SPP (sandpile prediction problem) y se muestra que los demás problemas son reducibles a tal problema. En los capítulos posteriores se estudia la restricción del modelo a las grillas de dimensión 1,2 y 3, mostrando los resultados más importantes referentes a la complejidad computacional de los problemas algorítmicos introducidos en el capítulo 2, en particular, como uno de los resultados de este trabajo, se exhibe un algoritmo en el capítulo 4 que proporciona una conjetura acerca de un problema abierto que aún se mantiene en dimensión 2 y que está estrechamente relacionado con el problema de la predicción.